Consider the following pseudo-code:

counter = 0
for (k = 16; k > 0; k /= 2)
    for (j = 0; j < k; j++)

I get that the time complexity is $O(n)$ when I examine the code, but I do have a question regarding the formal complexity analysis:

$$\begin{align} T(n) &= \sum_{i=1}^{\lceil \log_2 n \rceil} \sum_{j=1}^{2^i - 1} c = c \cdot \sum_{i=1}^{\lceil \log_2 n \rceil} (2^i - 1) \\ T(n) &= c\left( 2 \left[ 2^{\log_2 n} -1 \right] - \log_2 n \right)\\ T(n) &= c\left( 2n - 2 - \log_2 n \right)\\ T(n) &= \Theta(n) \end{align} $$

I understand outer loop must be $\log_2(n)$ but why do we say the inner loop's upper bound is $2^i$?

  • $\begingroup$ The i in the loop and the $i$ in the sum are two different things. You might want to rename one of them to $k$ in order to avoid confusion. $\endgroup$
    – nir shahar
    Nov 8 at 18:58

why do we say the inner loop's upper bound is $2^i$?

The outer sum (sigma) is going backwards, so to speak. The first iteration of the sigma makes the inner summation from $j=1$ to $j=1$, whereas, in fact, it should be from $j=1$ to $j=16$ (in your case).

In each iteration of the outer loop, we are doubling the variable $k$ from the outer for-loop (recall that we terminate the sum after $\log n$ iterations). Since $k$ is doubled, the inner sum (sigma), which corresponds to the inner for-loop needs to go from $j=1$ to $2^i$ to reflect the doubling of $k$.

  • $\begingroup$ Just for clarification, could you explain how are we doubling the variable k when we are dividing it? $\endgroup$ Nov 8 at 20:17
  • 1
    $\begingroup$ In the summation, the variable i is 1, 2, 3, 4, ..., log n instead of 1, 2, 4, 8, ..., n. Hence, to get the sum correctly, we take $2^i$ of the variable. $\endgroup$
    – Pål GD
    Nov 8 at 20:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.