Sorry for one small mistake in my analysis.
I forgot summation includes extreme values also, in the calculation.
So, final number of iteration is for
for(int i=1;i<=(n);i++)
for(int j=1;j<=(i*i);j++)
for(int k=1;k<=(j);k++)
{
}
But this mistake doesn't have any effect on the O(n^5) Time complexity. :)
:)
On Sat, Sep 10, 2011 at 5:10 PM, Kunal Patil <[email protected]> wrote:
> @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.
