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)