What is the time complexity of the following algorithm:

Question

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

Answer 1

TL;DR:
If this is indeed what is written in the book, then it is wrong. The time complexity is O(n).

Note:
As commented below - stricly speaking it is also O(nlogn), as well as O(n^2) etc. (because big-O only specifies an bound and not necessarily a tight one). But I assume we are interested in a tighter bound here.
Another implied assumption is that int calculations in this context are considered to have constant time - O(1). This is proper in most cases. But keep in mind that with current hardware, an integer of size n requires logn bits to represent.

More info:
The inner loop body (k++;) by itself is O(1), i.e. has contant time.
Therefore the complexity here is determined by the number of times the inner loop body is executed.

a in the outer loop will have the values:

n
n/2
n/4
...
1

The number of iterations of the inner loop is simply a mentioned above.

Therefore the total number of iteration of the inner loop will be:

n + n/2 + n/4 + ... + 1   

This is a decaying geometric series. It can be shown (the link contains the formulas) that if we assume n is large, then the sum is close enough to:

2n

Which is clearly O(n).

---

Note:
The exact sum is depedant on wether n is a power of 2 etc., but for the sake of big-O analysis the 2n approximation is good enough (because the discrepancy cannot amount to more than a constant factor).