CODEWITHSUNDEEP
javaalgorithmtime-complexitybig-ocomplexity-theory
Kyle Harte
Kyle Harte

Reputation: 33

How would I calculate big-O for this Algorithm

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?

Upvotes: 1

Views: 291

Answers (2)

dreamcrash
dreamcrash

Reputation: 51393

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

Upvotes: 1

0Interest
0Interest

Reputation: 1842

You are correct! This is basically a geometric progression with a quotient of 2 and the number of elements is lg(n) as we divide i by 2 each iteration of the outer loop.

1, 2, 4, ..., n

Using a known formula to calculate the sum, we get:

enter image description here

The reason we have lg (n) elements, is because we divide i each iteration by 2, thus we need to solve for the number of iterations k:

enter image description here

Upvotes: 1

Related Questions