# How to calcualte the Big-O complexity of the following algorithm?

I have been trying to calculate the Big-O of the following algorithm and it is coming out to be O(n^5) for me. I don't know what the correct answer is but most of my colleagues are getting O(n^3).

for(i=1;i<=n;i++)
{
for(j=1 ; j <= i*i ; j++)
{
for(k=1 ; k<= n/2 ; k++)
{
x = y + z;
}
}
}


What I did was start from the innermost loop. So I calculated that the innermost loop will run n/2 times, then I went to the second nested for loop which will run i^2 times and from the outermost loop will run i times as i varies from 1 to n. This would mean that the second nested for loop will run a total of Sigma(i^2) from i=1 to i=n so a total of n*(n+1)*(2n+1)/6 times. So the total amount that the code would run came out to be in the order of n^5 so I concluded that the order must be O(n^5). Is there something wrong with this approach and the answer that I calculated?

I have just started with DSA and this was my first assignment so apologies for any basic mistakes that I might have made.

• I don't follow so a total of ($O(n^3)$) in combination with total [came out] $O(n^5)$ - can you present each step? Aug 30 '20 at 6:55
• I multiplied the times all the loops run. 1st loop runs n times, 2nd one runs (2n^3 + 3n^2 + n)/6 times and the 3rd one runs n/2 times. So the maximum degree of n comes out to be 5 on multiplication. Aug 30 '20 at 8:33
• "loose language" and, depending on interpretation, not the way to go. For the third one see, e.g., BearAqua's answer. Aug 30 '20 at 8:51

for(i=1;i<=n;i++)
{
for(j=1 ; j <= i*i ; j++)
{
for(k=1 ; k<= n/2 ; k++)
{
x = y + z;
}
}
}



The triple-nested loop is equivalent to the summation $$\sum_{i=1}^{n}\sum_{j=1}^{i^2} \sum_{k=1}^{n/2} 1$$ $$=\frac{n}{2}(\sum_{i=1}^{n}\sum_{j=1}^{i^2}1)$$ $$=\frac{n}{2}(\sum_{i=1}^{n}i^2)$$ $$=\frac{n}{2} \cdot (\frac{1}{6}n(n+1)(2n+1))$$ $$=O(n^4)$$

In terms of actual code efficiency, since x=y+z is invariant in the loop, any good optimizing compiler will extract the statement out of the loop (in compiler-speak, hoist the statement to loop preheader), hence making the compiled code run in $$O(1)$$.

• can this summation method be used for calculating the order of all multiple nested loop problems? Aug 30 '20 at 8:51
• @RavishJha I wouldn't really call it a "method", but it depends on how you define "all multiple nested loop problems." For instance, it becomes more complicated when recursion is involved in the inner loop. Aug 30 '20 at 15:19