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)
Number of times statement is executed in complex nested loop
algorithm analysis;time complexity;asymptotics;runtime analysis
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.