Question #186817
  • 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++
1
Expert's answer
2021-04-29T23:53:17-0400

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(n2)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(n2)+O(n2)=O(n^2)+O(n^2)

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


Need a fast expert's response?

Submit order

and get a quick answer at the best price

for any assignment or question with DETAILED EXPLANATIONS!

Comments

No comments. Be the first!
LATEST TUTORIALS
APPROVED BY CLIENTS