thnx

Dark Mode

166 views

1 vote

Best answer

Note: i runs from 0 to n-1 , j run from i to i^2 – 1 and k from 0 to j-1

So, For i=0 and 1 , j will not run at all.

For i=2, j from 2 to 3 but will enter if statement only for j=2 so k runs from 0 to 1…... [2 times]

For i=3, j from 3 to 8 but if statement valid for only j=3,6 so k runs from 0 to 2(for j=3) and 0 to 5 (for j=6) ……..[(3+6) times= 3*(1+2) times]

so if you look at the pattern ….

For i=4 …….. [4*(1+2+3) times]

For i=5 ……...[5*(1+2+3+4) times]….. and so on

you forgot to multiply $j$ in step $\sum_{j=2}^{n-1} (j-1)j/2$ from step $\sum_{j=2}^{n-1} j * \sum_{k=1}^{j-1}k$.

Generally, when we find any pattern, we have to prove it. Here it is easy to prove by induction.

For, $i=k,$ $T(k) = k \sum_{p=1}^{k-1}p = \frac{k*k*(k-1)}{2}$

Now, for $i=k+1,$ $T(k+1) = (k+1) \sum_{p=1}^{k}p = \frac{(k+1)*(k+1)k}{2}$

(+1) for the Answer.

Generally, when we find any pattern, we have to prove it. Here it is easy to prove by induction.

For, $i=k,$ $T(k) = k \sum_{p=1}^{k-1}p = \frac{k*k*(k-1)}{2}$

Now, for $i=k+1,$ $T(k+1) = (k+1) \sum_{p=1}^{k}p = \frac{(k+1)*(k+1)k}{2}$

(+1) for the Answer.

1