CODEWITHSUNDEEP
for-looptime-complexity
shinzou
shinzou

Reputation: 6232

Analyzing nested for loops

Analyze the runtime complexity of:

for(i=1; i <= n; i=i*2)
  for(j=1; j<= n-i; j++)
    print j;

My try:

Writing down the values for i,j:

i:  1       |   2        |  …|  2^i     |...| 2^log_2(n)=n

j:  1...n-1 |   1...n-2  |   | 1...n-2^i|...| 0

So I get the following:

enter image description here

Is this right? I'm really not sure about the change of variable and the middle sum.

Upvotes: 1

Views: 178

Answers (1)

JDong
JDong

Reputation: 2304

We will look at each part of the loop separately.

The outer loop may be represented as:

for(i=1; i <= n; i=i*2)
    f(n, i)

Where f(n,i) is the inner loop with complexity O(f). This has a complexity of log(n) * O(f).

for(j=1; j<= n-i; j++)
    print j;

This has a complexity of n, since n dominates i. i is a power of two less than n, and so their difference is at worst n - 1.

Thus the complexity is log(n) * n or nlog(n).

Upvotes: 1

Related Questions