Time Complexity Sigma Notation

Question

Consider the following pseudo-code:

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

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$?

• nir shahar: 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.

Answer 1

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$.

• pinkymartini: Just for clarification, could you explain how are we doubling the variable k when we are dividing it?
• Ainsley H.: 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.