retagged by
413 views

2 Answers

Best answer
3 votes
3 votes

$\large\color{red}{O(n^4)}$

selected by
3 votes
3 votes

j is depend upon i and k is depend upon i and j ===> we have to unroll the dependency

when i=1

j=1 ===> k=1

 

when i=2

j=1 ===> k didn't run

j=2 ===> k run 2 times

j=3 ===> k didn't run

j=4 ===> k run 4 times

∴ 2+4 == 2(1+2)

 

when i=3

j=1 ===> k didn't run

j=2 ===> k didn't run

j=3 ===> k run 3 times

j=4 ===> k didn't run

j=5 ===> k didn't run

j=6 ===> k run 6 times

j=7 ===> k didn't run

j=8 ===> k didn't run

j=9 ===> k run 9 times

∴ 3+6+9 == 3(1+2+3)

.......

when i=p

j=1 ===> k didn't run

j=2 ===> k didn't run ......

j=p ===> k run p times 

j=p+1 ===> k didn't run

j=p+2 ===> k didn't run .............

j=2p ===> k run 2p times

j=2p+1 ===> k didn't run

j=3p ===> k run 3p times ..............

j=p*p ===> k run p*p times

∴ p+2p+3p+......+p2 == p(1+2+3+....+p)

 

Total = 1 ( 1 ) + 2 . ( 1+2 ) + 3. ( 1+2+3 ) + ......+ p . ( 1+2+3+....+p ) +....... + n . ( 1+2+....+n )

from these observations we can conclude that

Time complexity = $\LARGE \sum_{i=1}^{n} ( i$$\sum_{j=1}^{i} j \LARGE) $

                          = $\LARGE \sum_{i=1}^{n} ( i$ ( 1+2+3+...i )$ \LARGE) $

                          = $\LARGE \sum_{i=1}^{n} ( i$ $( \frac{i(i+1)}{2} $ $ \LARGE) $

                          = $\frac{1}{2}\LARGE \sum_{i=1}^{n} ( i^{3} + i^{2} $ $ \LARGE) $

                          = O(n4)

note that summation of first n natural cubes =$ {( \frac{n(n+1)}{2}) }^{2}$

Answer:

Related questions

0 votes
0 votes
1 answer
1
Anuj1995 asked Jan 10, 2019
472 views
What is the right answer?
2 votes
2 votes
1 answer
2
thepeeyoosh asked Jan 11, 2018
1,011 views
1 votes
1 votes
1 answer
3
nikkey123 asked Jan 3, 2018
370 views
1 votes
1 votes
1 answer
4
Kaluti asked Dec 6, 2017
663 views