# 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? – greybeard 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. – Ravish Jha 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. – greybeard 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? – Ravish Jha 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. – BearAqua Aug 30 '20 at 15:19