Answer to Question #186817 in Algorithms for Haider

Question

• Analyze the time complexity of the following segments Analyze the time complexity of the following segments 
• Program:
• sum1=0;
• for(k=1;k<=n;k*=2)
• for(j=1;j<=n;j++)
• sum1++
• sum2=0;
• for(k=1;k<=n;k*=2)
• for(j=1;j<=k;j++)
• sum2++

Answer 1

Given,

sum1=0;
for(k=1;k<=n;k*=2)
for(j=1;j<=n;j++)
sum1++
sum2=0;
for(k=1;k<=n;k*=2)
for(j=1;j<=k;j++)
sum2++

From the analysis, one for loop have O(n) time complexity.

If there is two for loop in the nested form then it will have $O(n^2)$ time complexity.

but here two nested form loop are initiated one by one.

Hence, time complexity of the function will be $=O(n^2)+O(n^2)$

Hence the required time complexity of the function will be $O(n^2)$