0

I was trying this below code to find the time complexity and somewhere Lecturer said that here you have same variable name so time complexity would be O(n^3) , I think it should be O(n^6) can someone help me Iam confused

int i ;
for(i=1;i<=n;++i)
{
for(i=1;i<=n^2;++i)
{
for(i=1;i<=n^3;++i)
{
x=y+z;
}
}
}
Sumit Goyal
  • 5
  • 3
  • `j` is unassigned? – Mathias R. Jessen May 23 '20 at 14:45
  • sorry by mistake I put j it should be i let me edit it sir – Sumit Goyal May 23 '20 at 14:47
  • 1
    Does this answer your question? [Big O, how do you calculate/approximate it?](https://stackoverflow.com/questions/3255/big-o-how-do-you-calculate-approximate-it) – Paul Hankin May 23 '20 at 14:49
  • This is O(n^3) because first and second loop will be executed only once. – DevO May 23 '20 at 14:50
  • Here the 3rd `for` loop will run completely when it finishes the other two for loops conditions will fail. So Time complexity will be the complexity of 3rd for loop: O(n^3) – thuva4 May 23 '20 at 14:50
  • no no my question is totally different had the variable name in for loop is different complexity will be O(n^6) , I solved this problem a year ago in which lecturer said here variable name in each for loop is same so time complexity will be O(n^3) this i i want to know how – Sumit Goyal May 23 '20 at 14:51
  • @thuva4 isn't it should be n*n^2*n^3 = O(n^6) where iam going wrong please clarify sir – Sumit Goyal May 23 '20 at 14:54
  • ok I got it thanks to debug feature of turbo c – Sumit Goyal May 23 '20 at 15:03

1 Answers1

0

The first for loop starts, then the second and the third. The third for loop runs until i>n³. Once this happens, the second for loop will finish one iteration, it then tries to check if i<=n², but since i > n³, it ends the loop. This happens for the first loop as well.

This happens mainly because the i variable is block scoped and since all three loops are nested, they all share the same variable.

Aanu Babajide
  • 83
  • 6