Reputation: 6232
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:
Is this right? I'm really not sure about the change of variable and the middle sum.
Upvotes: 1
Views: 178
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