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

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