algorithm

Question

sum = 0;
for( i = 0; i < n; i++)

for( j = 0; j < i*i; j++)

 

for( k = 0; k < j; k++)

 

sum++;

 

how to solve this  :( help someone    time complexity = o(n^5 )  how ??

Answer 1

try to find out for each i, how many times innermost for-loop loops through

for i=0, j will go from 0-0, and k = 0 times

for i=1, j will go from 0, 1 and for each j i'e  j=0, k= 0 times, for j=1, k= 1 times . so total ( 0 + 1) times

similarly for i = 2 check the below image --

 

Comments

@Sumit goyal, You are correct

But

since we are more interested in finding asymptotically​ upper bound, so i  ignored them to just to easily understand it

---

bhai can u please solve it , without ignoring them pleasee ,

---

Why it is O(n^5) not O(n^4)?

Answer 2

The running time for the operation sum++ is a constant. 
The most inner loop runs at most n^2 times, the middle loop also runs at most n^2 times, and the outer loop runs n times, thus the overall complexity would be O(n⁵).

Comments

thanku bhai

Answer 3

think this way

1)sum = 0;
for( i = 0; i < n; i++)

sum++

this executes  n times look like

        n-1
        ---            
        \                      
        /   1  =   n-1   So T(n) = O(n)
        ---            
        i=1 

this executes  n times

2)sum = 0;
for( i = 0; i < n; i++)

for( j = 0; j < i*i; j++)

sum++

        n-1    i^2-1        n-1
        ---   ---          ---
        \     \            \      
        /     /    1  =    /    i^2-1  =    So T(n) = O(n^3)
        ---   ---          ---
        i=0   j=0          i=0

let consider loop imitial condition start from 1

3) sum = 0;
for( i = 1; i <= n; i++)

for( j = 1; j <= i*i; j++)

 for( k = 1; k <= j; k++)
 
sum++;

      n     i^2         j                  n      i^2                   n  
        ---   ---         ---               ---     ---                    ---
        \     \           \                  \        \                    \ 
        /     /           /    1    =      /         /    j  =        /   i²(i²+1)/2            
        ---   ---         ---               ---        ---                 ---
        i=1   j=1      k=1         i=1       j=1                   i=1

then 

         n
        ---            
        \                      
        /   (i⁴+i²)/2 =   
        ---            
        i=1 

Sigma n^4 = n*(n+1)*(2*n+1)*(3*n2+3*n-1)/30 =O(n5)

Sigma (n^2) = n(n+1)(2n+1)/6 =O(n³)

so overall O(n⁵)

Comments

thanku bhai