Algorithm

Question

Consider the following program segment?
```
main ()
\{
int $i=0$; int $c=0$;
For $(i=1 ; i \leq n ;++i)\{$
For $\left(j=1 ; j \leq i^{*} i ;++j\right)\{$
If $((j \% i)==0)$
For $(k=1 ; k \leq j,++k)\{$
$c=c+1$
\}
\}
\}
\}
```

Which of the following will represent time complexity of above program segment?

• A. $\mathrm{O}\left(n^{3}\right)$
  
• B. $O\left(n^{4}\right)$
  
• C. $O\left(n^{2}\right)$
  
• D. $O\left(n^{5}\right)$

Answer 1

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

Comments

@debashishDeka plz could u elaborate  it little more i am getting confused with this ans...plz help in other way..thanks

Answer 2

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+......+p² == 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(n⁴)

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

Comments

Great explanation