# 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)

• I don't understand your first summation. Why does k go from 1 to log(n)+1? In the for loop, k goes like n, n/2, n/4, etc. – skankhunt42 Feb 19 '17 at 17:55
• It can also be k = 0 to log(n). Anyway, what I understood was log(n) denotes the max number of iterations the outer loop performs. – user3930057 Feb 20 '17 at 3:35
• It's the number of iterations, but you need the values k. – gnasher729 Feb 20 '17 at 13:58

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.

• How did this happen? $$\sum_{u\in S}\sum_{h=0}^{\lambda}\lfloor2^{u-h}\rfloor = \sum_{u\in S}2^{u+1}-1$$ – user3930057 Feb 21 '17 at 5:45
• @user3930057 Sum of a geometric progression. I omitted the denominator since it is (2-1)=1. – quicksort Feb 21 '17 at 9:01
• Using sum of geometric progression, doesn't it become like this?$$\sum_{h=0}^{\lambda}\lfloor2^{u-h}\rfloor = 2^{u+1}-2^{u-n}$$ – user3930057 Feb 21 '17 at 9:22
• @user3930057 No. Where does $n$ come from, by the way? – quicksort Feb 21 '17 at 9:27
• Sorry, I meant this $$\sum_{h=0}^{\lambda}\lfloor2^{u-h}\rfloor = 2^{u+1}-2^{u-\lambda}$$ – user3930057 Feb 21 '17 at 9:29

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