397 views

1 Answer

2 votes
2 votes
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})$

 

edited by
Answer: