0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – greybeard Aug 30 at 6:55
  • $\begingroup$ 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. $\endgroup$ – Ravish Jha Aug 30 at 8:33
  • $\begingroup$ "loose language" and, depending on interpretation, not the way to go. For the third one see, e.g., BearAqua's answer. $\endgroup$ – greybeard Aug 30 at 8:51
2
$\begingroup$
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)$.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ can this summation method be used for calculating the order of all multiple nested loop problems? $\endgroup$ – Ravish Jha Aug 30 at 8:51
  • $\begingroup$ @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. $\endgroup$ – BearAqua Aug 30 at 15:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.