m=1;
for(i=1;i<=n;i++){
m=m*2;
for(j=1;j<=m;j++){
do something that is O(1)
}
}
What will be time complexity of the above code ?? Please tell me how to solve these types of problem.
Add a comment
|
3 Answers
I prefer to look at these problems from the inside out. Removing the m, we have:
for(i=1;i<=n;i++){
for(j=1;j<=2^i;j++){
do something that is O(1)
}
}
Or:
for(i=1;i<=n;i++){
O(2^i)
}
So overall: sum_1^n O(2^i)=O(2^(n+1))=O(2^n).
Comments
Inner loop will iterate 1 time, then 2 times, then ..., then 2^n times. So we have 1 + 2 + 4 + ... + 2^n = 2^(n + 1) - 1 = O(2^n) iterations of inner loop.
One iteration of inner loop has constant complexity, so summed_inner_loop_complexity = O(2^n).
Whole complexity is O(2^n).
2 Comments
Teepeemm
No. You can multiply by
n, or get the summed inner loop complexity (better), but both means you're over counting. The answer should be O(2^n).
Ashok Naval
I think it should be O(2^n) as Teepeemm has explained.
Formally and methodically, you can use Sigma notation:
answered Jun 6, 2014 at 20:30
Mohamed Ennahdi El Idrissi
2,9872 gold badges21 silver badges35 bronze badges