int k = 0;
for (int a = n; a >= 1; a /= 2)
for (int b = a; b >= 1; b--)
k++;
cout << k;
I would say that the answer is O(n), but the book where I have found the exercise says that the right answer is O(nlogn).
Personally, I like to solve these questions in a mathematical way:
You can find the number of times the first loop runs with this formula:
1 = n*2^(-i)
Where i is the number of loops of the first for loop. In reality, it is not equal, but equal to or less than, but it doesn't really matter for this.
Rearranging we get this:
i=log(n)
So this means the first loop is log(n). The log has a base of 2.
Next, it is important to understand how the second loop works. The second loop does not run n times every time, it changes. Since it uses the variable a from the first loop, it depends on the current state of this variable. Now it gets a little tricky, as the number of loops must be written as a sum.
\sum_{r=0}^{log(n)} 2^{-r}n
You can go to desmos, copy the expression above and put y= before it to get a nice, but choppy, graph. The sum, loops the same amount of times as the first loop, which is log(n) as previously calculated. The inside expression is the amount of times the second loop, loops. It is actually just how the variable a is calculated in the code, but this is how many times it runs.
Now, after all this, you can see the graph of the sum, is the same as y = 2n, meaning that the time complexity is O(n). The reason the book states something else, I am not quite sure, but I believe some other users have posted some brief explanation about this.
By the way, I also verified this result with the code you presented, and found that it does follow the O(n) time complexity.