# Time Complexity Sigma Notation

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

• 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. 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$$.
• 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. Nov 8 at 20:27