Big Oh Notation Time Complexity

Question

i = log(n)

while(i > 0) {
  for(j = 1;j <= exp(2,i);j++) {
    <do some constant time operations>
  }
  i--;
}

I think the big oh notation would be O(n*log(n)) because the outer loop is log(n) and the inner loop at most would be 2^log(n) = n and then decrease each iteration. Am I right ?

Answer 1

When considering the inner loop, there will be $$2^{i}, 2^{i-1}, 2^{i-2}, ... , 2^{2}, 2$$ or $$n, \frac{n}{2}, \frac{n}{4}, \frac{n}{8}, .., [\frac{n}{2^{i - lg(n) + 1}} = 2]$$ number of iterations for each decrement of $i$, depending on how you'd like to look at it.

So then, summing these terms yields a closed form formula, which can then be classified with $O$.

$$\sum_{i=1}^{lg(n)}2^{i} = 2^{lg(n) + 1} - 2 \in O(n)$$

used the geometric series formula.

---

I believe the error in your approach was only considering the largest value of $j$, which is the first pass through the while-loop, instead of including all passes through the while-loop, a process that involves summing the # of iterations that the for-loop performs for every decrement of $i$.