Calculate the complexity of a nested for loop

Question

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?

Try looking through this: stackoverflow.com/questions/8331479/determining-big-o-notation I doubt anyone will just give you the answer. — Seth Moore
– Seth Moore, Commented Mar 15, 2013 at 13:17
@smoore: The value of i in the inner loop is bounded above by n. — Fred Foo
– Fred Foo, Commented Mar 15, 2013 at 13:30
@smoore: happens all the time. I wasn't going to post one until I saw incorrect answers popping up. — Fred Foo
– Fred Foo, Commented Mar 15, 2013 at 13:33

Fred Foo · Accepted Answer · 2013-03-15 13:26:52Z

3

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

answered Mar 15, 2013 at 13:26

Fred Foo

365k80 gold badges765 silver badges852 bronze badges

Sign up to request clarification or add additional context in comments.

4 Comments

user1952500 Over a year ago

Many books consider the latter notation to mean log log n

Fred Foo Over a year ago

@user1952500: I've never seen that use of lg² n, but that's exactly why I gave both notations (see also math.se).

SomeWittyUsername Over a year ago

loglogn means log(logn) while log^2(n) means logn*logn

SomeWittyUsername Over a year ago

While the result is correct, the analysis is crude and could easily miss the tightest bound.

Eric · Accepted Answer · 2013-03-15 15:58:49Z

2

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)

edited Mar 15, 2013 at 15:58

Eric

98.1k54 gold badges257 silver badges389 bronze badges

answered Mar 15, 2013 at 14:53

Eric Leschinski

155k96 gold badges423 silver badges337 bronze badges

2 Comments

Eric Over a year ago

Your conclusion does not match your results. num_times_inner_loop_part_runs = n(n + 1) / 2. Perhaps you had i++ instead of i*=2

Eric Leschinski Over a year ago

ooh the increment is j*=2. I fixed it.

SomeWittyUsername · Accepted Answer · 2013-03-17 19:54:44Z

1

Time analysis of this piece of code:

Analysis

answered Mar 17, 2013 at 19:54

SomeWittyUsername

18.4k3 gold badges46 silver badges87 bronze badges

Comments

Mohamed Ennahdi El Idrissi · Accepted Answer · 2014-03-17 15:51:26Z

0

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.

edited Mar 17, 2014 at 15:51

answered Mar 17, 2014 at 15:20

Mohamed Ennahdi El Idrissi

2,9872 gold badges21 silver badges35 bronze badges

Collectives™ on Stack Overflow

Calculate the complexity of a nested for loop

4 Answers 4

4 Comments

2 Comments

Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

4 Answers 4

4 Comments

2 Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related