Number of times statement is executed in complex nested loop

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)

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.

StackExchange Computer Science Q#70516, answer score: 8