@Piyush: In 2 ways I will prove you wrong.
1)
Lets take 2 innermost loops.
for(j=0;j<i*i;j++)
{
for(k=0;k<j;k++)
}
Let i*i be m. Thus, It becomes.
for(j=0;j<m;j++)
{
for(k=0;k<j;k++)
}
You would agree that this is O(m^2).
This means innermost two loops constitute O(m^2) --> O(( i^2) ^ 2) --> O(i ^
4)
Outer loop iterates over i once till n.
So,
for i=0 it will run O(i^4=0) times
for i=1 it will run O(i^4=1) times
for i=2 it will run O(i^4=16) times
for i=n it will run O(n^4) times.
Summing all them up, its O(n^5).
2)
Lets represent given loops by summations:
for(i=0;i<n;i++) --> summation_i_from_0_to_n
{
for(j=0;j<i*i;j++) --> summation_j_from_0_to_i^2
{
for(k=0;k<j;k++) --> summation_k_from_0_to_j
So To calculate exact number of iterations you would need to solve these
nested summations.
Steps:
1) Initially we have,
summation_i_from_0_to_n ( summation_j_from_0_to_i^2
(summation_k_from_0_to_j (constant) ))
2) Innermost summation evaluates to j
So now we are left with -->
summation_i_from_0_to_n ( summation_j_from_0_to_i^2 ( j ) )
3) Innermost evaluates to (i^2)*(i^2 + 1) /2
So now we are left with -->
summation_i_from_0_to_n ( (i^2)*(i^2 + 1) /2 )
4) This evalutes to
(1/2) { (6*n^5 + 15n^4 + 10n^3 - n) / 30 } + (1/2) { n*(n+1)*(2n+1) / 6 }
which is equal to the exact number of iterations.
This is clearly O(n^5).
Correct me If I am wrong anywhere in the analysis...
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
