How would I calculate big-O for this Algorithm

Question

I have got this algorithm

int count = 0;
for(int i = n; i >= 1; i = i/2) {
   for ( int j = 1; j <= i; j++) {
      count++;
   }
}

Am I right in saying that the Big-O for this would be n/2?

Answer 1

TL;DR The time complexity is O(n).

More details

Am I right in saying that the BigO for this would be n/2?

No that is accurate, in big-O notation you drop the constant part so (1/2)n simplifies to O(n).

I am not sure where that n/2 comes from because only the outer loop

for(int i = n; i >= 1; i = i/2) {
   ...
}

is log2n not n/2.

And with both loops together:

int count = 0;
for(int i = n; i >= 1; i = i/2) {
   for ( int j = 1; j <= i; j++) {
      count++;
   }
}

the count would vary between N and 2N.

Let us go through the calculations:

int count = 0;
for(int i = n; i >= 1; i = i/2) {
   for ( int j = 1; j <= i; j++) {
      count++;
   }
}

The inner loop will execute N iterations then N/2, then N/4 ... until N/N.

In another words we have (N + N/2 + N/4 ... N/N) which can be simplified to N * (1/2 + 1/4 + .. + 1/2^L)), with L = Log2 N.

This (1/2 + 1/4 + .. + ) series is well-known for being 1. Therefore, we can simplified N * (1/2 + 1/4 + .. + 1/2^L)) to O(N).