Why is this algorithm linear and not linearithmic?

Question

int sum = 0; 
for (int n = N; n > 0; n /= 2)
   for (int i = 0; i < n; i++)
      sum++; 

I was pretty sure it grows in nlogn but was told it's linear... Why is it linear and not linearithmic?

Answer 1

It is linear. Imagine for a second n is 64. The inner loop runs 64 times, then 32 times, then 16 times, then 8 times, then 4 times, then 2 times, then 1 time. 64 + 32 + 16 + 8 + 4 + 2 + 1 = 127.

So it requires 2n-1 total operations (for a power of 2, but that doesn't change the analysis), assuming the inner loop is not optimized away. That's clearly O(n) -- linear.

If the inner for loop is optimized away (to sum += n;), it's logarithmic.

Answer 2

The complexity of this algorithm is Θ(N).

The number of operations is

sum{2**k} for k = 0..log2(N)

The sum of this progression is

2*N-1

which is Θ(N).

Answer 3

Formally, using Sigma Notation can help you to see clearly that the order of growth is linear.