I am having difficulty trying to find the total number of operations in the following code block:

for(int i = 1; i <= n; i *= 2) {
   for(int j = 1; j <= i; j *= 2) {
       // What is the number of operations here, with respect to n?
   }
}

My thinking was that: there are floor(log_2(n)) operations in the outer loop, and log_2(i) operations in the inner loop. I am not sure if my thinking is right, and how I would go from here... How could this be written in terms of solely n?

CodePudding user response：

As you said, there are floor(log_2(n)) operations in the outer loop. For simplicity let's say log_2(n) operations. It won't matter so much for the large number of inputs. In the inner loop, number of operations will be log_2(i) for each case.
So, from i=1 to i=n, number of inner loop operations:
log_2(1) log_2(2) log_2(3) ... log_2(n)
By logarithm rules: log(a) log(b) = log(a*b)
total number of operations = log_2(n!)
Notice that base of the logarithms are assumed to be 2 in computer science if we are talking about time complexities.
In short, time complexity of the algorithm will be : O(log(n!))

What is O(log(n!)) anyways? Well here's a little trick to compare it with a more familiar time complexity:
Note that:
log(1) log(2) ... log(n) <= log(n) log(n) ... log(n) = n*log(n)
therefore, log(n!) <= n*log(n) (upper bound)
and by the definition of Big-Oh notation, O(log(n!)) ⊆ O(n*log(n))
So we can also say that, time complexity of this algorithm can be shown as O(n*log(n)).