How to calcualte the Big-O complexity of the following algorithm?
-
29-09-2020 - |
Question
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.
Solution
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)$.