Number of times statement is executed in complex nested loop

Question

I am trying to find out how many times the "statement" is executed by finding its formula based on these loops:

int s = 0;
for(int k = n; k > 0; k /= 2)
{
  for(int l = k; l < n; l++)
  {
    s++; // statement
  }
}

I have been stuck with this problem for a while since I couldn't really get the correct formula whenever I compared the result of my formula to the output s.

I started by doing this:

$$T(n) = \sum_{k=1}^{\left\lfloor{\log_2(n)}\right\rfloor + 1}\sum_{l=k}^{n-1} 1$$

then eventually got this as a result:

$$T(n) = (1/2)(\left\lfloor{\log_2(n)}\right\rfloor + 1)(2n - \left\lfloor{\log_2(n)}\right\rfloor-2)$$

Does anyone know how to solve this kind of problem?

(This is a self-made problem btw since I kind of find analysis of algorithms fun)

Answer 1

We can determine the exact value of $s$ as a function of $n$. For the sake of brevity, let $\lambda = \left \lfloor \lg n \right \rfloor$. We can replace the inner loop with:

$s \leftarrow s+n-k$

At the end of the program we'll have:

$$ s= \sum_{h=0}^{\lambda} n - \left \lfloor \frac{n}{2^h} \right \rfloor = n \left( \lambda + 1 \right) - \sum_{h=0}^{\lambda} \left \lfloor \frac{n}{2^h} \right \rfloor $$

Our problem is now rewriting the last term in a nicer form. . Certainly $n$ has a unique representation in base $2$, in particular it is true that

$$ n = \sum_{u \in S} 2^u $$

for some $S \subseteq \mathbb{N}_{\le \lambda}$.

Therefore we have:

$$ \sum_{h=0}^{\lambda} \left \lfloor \frac{n}{2^h} \right \rfloor = \sum_{h=0}^{\lambda} \sum_{u \in S} \left \lfloor 2^{u-h} \right \rfloor = \sum_{u \in S} \sum_{h=0}^{\lambda} \left \lfloor 2^{u-h} \right \rfloor = \sum_{u \in S} 2^{u+1} -1 $$

But then:

$$ \sum_{u \in S} 2^{u+1} -1 = 2n - |S| $$

Piercing it all together, at the end of the program we will have:

$$ s = n \left ( \left \lfloor \lg n \right \rfloor - 1\right) + \textbf{1}(n) $$

where $\textbf{1}(n)$ is the Hamming norm of $n$, that is, the number of ones in its binary representation.

Answer 2

The outer loop runs about log n times.

The inner loop runs 0 times during the first iteration when k = n. All the other times, 0 ≤ k ≤ n/2, so the inner loop runs between n/2 and n times, so we have O (n log n).