1
$\begingroup$

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

$\endgroup$
1
  • $\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, 2021 at 18:58

1 Answer 1

1
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ Just for clarification, could you explain how are we doubling the variable k when we are dividing it? $\endgroup$ Nov 8, 2021 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, 2021 at 20:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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