CODEWITHSUNDEEP
for-loopbig-ocomplexity-theorynested-loops
Sarah Zeftawy
Sarah Zeftawy

Reputation: 39

Calculate the complexity of a nested for loop

I want to calculate the complexity of this nested for loop:

s = 0;
for(i=1; i<=n; i*=2)
   for(j=1; j<=i; j*=2)
      s++;

What strategy do I use to find the Big O complexity of this piece of code?

Upvotes: 2

Views: 2773

Answers (4)

Mohamed Ennahdi El Idrissi
Mohamed Ennahdi El Idrissi

Reputation: 2977

Your algorithm time complexity can be portrayed formally as the following:

enter image description here

This document (last slide) might be enormously useful to you.

Upvotes: 0

SomeWittyUsername
SomeWittyUsername

Reputation: 18338

Time analysis of this piece of code:

Analysis

Upvotes: 1

Eric Leschinski
Eric Leschinski

Reputation: 153822

Strategy for getting the answer yourself

Plug in different values of n into the equation, and make a chart of how many times the innermost part of the loop runs:

s = 0;
for(i=1; i<=n; i*=2)
  for(j=1; j<=i; j*=2)
    s++;

Something like this:

n     num_times_inner_loop_part_runs
1     1
2     3
3     3
4     6
5     6
6     6
7     6
8     10
9     10
...
15    10
16    15
...
31    15
32    21

You can get these data points with a program like this:

int n = 9;  //change this n
int counter = 0;
for(i=1; i<=n; i*=2){
  for(j=1; j<=i; j*=2){
    s++;
    counter++;
  }
}
cout << "counter is: " <<  counter << endl;

Plot the num_times_inner_loop_part runs on an X/Y coordinate plane and you'll see a curve.

Name the curve that fits closest. In this case, it is X = (log(Y)^2)

If you plot your data and X = (log(Y)^2), you'll find they should overlap each other.

Therefore, the complexity of this function is O((log(n))^2) which is an improvement over O(n)

Upvotes: 2

Fred Foo
Fred Foo

Reputation: 363487

The outer loop marches through 1, 2, 4, 8, ... n, which takes O(lg n) steps because you can only double one O(lg n) times until you hit n.

The inner loop does the same. It only goes up to i, but in the final iteration of the outer loop, i reaches its maximum value which is again n, so that's also O(lg n).

Putting this together gives an upper bound of O((lg n)²), which is commonly abbreviated O(lg² n).

Upvotes: 3

Related Questions