in Algorithms
137 views
0 votes
0 votes

How to approach for this question?

in Algorithms
137 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

4 Comments

How’s n related to i and j?

Also, how are i and j related to the time complexity of the code?
0
0

@Arjun sir the value of outer loop(i)  ranges from 1 to n and depending on the value of i we calculate the number of turn (j) which the inner loops execute.

here i and j are related to the time complexity as the summation of total number of times the inner loops runs for each iteration of the outer loop is our desired time complexity .Depending on that result we can comment on the asymptotic notation.

I have edited my answer . is it correct now?

1
1
yes, now fine. Basically we are counting the number of times printf is happening as that statement is the most executed one. ((j <= p) conditional will actually execute one extra time)

The steps given are essential if the question asks for the exact term. For asymptotic time complexity you might be able to skip a few steps.
0
0
Yes sir  understood . Thank you.
1
1