i |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
j |
1+3 |
4+4 |
8+5 |
13+6 |
19+7 |
26+8 |
34+9 |
43+10 |
53+11 |
The following table tell us how i and j are related.
basically for each i in the outer loop the inner loop j runs for p times where p=p+i+2.
when i=1 the inner loop run for 4 time as p=4 as p=p+i+2 here initially p=1,i=1 here so p=4.
when i=2 the inner loop run for 8 time as p=p+i+2 , p=4 i=2.
and so on .
now we have add all these values to know total how many times the loop runs.
so our summation S would be ,
$S=4+8+13+19+.......+Tn$
now we have to find the nth term which is T(n).
now if you see carefully we can draw a recurrence relation to calculate the nth term ,
$T(n)=T(n-1)+n+2$ ,n>1
=4 ,n=1
$T(n)=T(n-1)+n+2$
=>$T(n)=T(n-2)+(n-1)+2+n+2$
=>$T(n)=T(n-3)+(n-2)+2+(n-1)+2+n+2$
=>$T(n)=T(1)+2+2+3+2+.........+(n-1)+2+n+2$
=>$T(n)=T(1)+1+2+3+4+....+(n-1)+n+2(n-1)-1$
=>$T(n)=4+\frac{n*(n+1)}{2}+2n-3$
=>$T(n)=\frac{n^{2}+5n+2}{2}$
so we have found our nth term.
So to get the sum of series we use summation operator on our Tn.
$S=\frac{1}{2}\sum (n^{2}+5n+2)$
$S=\frac{1}{2}\left \{\sum n^{2}+5\sum n+\sum 2 \right \}$
$S=\frac{1}{2}\left \{ \frac{n(n+1)(2n+1)}{6}+5*\frac{n(n+1)}{2}+2n\right \}$
$S=\frac{2n^{3}+18n^{2}+28n}{12}$
correct option is $\Theta (n^{3})$