i am kind of confuse in this i know in outer loop if i < n and in inner loop if j < i then the complexity will be O(n^2) but if we increase the limit from n and i respectively to n^2 and i^2 does the complexity doubles like O(n^4) or does it becomes cubic O(n^3) ?
for(long i = 1; i < n*n; i )
{
for(long j = 1; j < i * i; j )
{
//some code
}
}
CodePudding user response:
Assuming that //some code
takes O(1)
operations, the time complexity is O(n^6)
. Since the inner loop takes i^2 - 1
iterations, you can use the sum of squares formula (or equivalently use Wolfram alpha) to get