in Algorithms edited by
213 views
1 vote
1 vote
BigO notation of

T(n)=T(n-1)+ √n     ; n>=1

       =0.        ; Otherwise
in Algorithms edited by
by
213 views

1 Answer

5 votes
5 votes
Given ,

$T(n)=T(n-1)+\sqrt{n} ;n\geq 1$

$T(n)=T(n-2)+\sqrt{n-1}+\sqrt{n}$

$T(n)=T(n-3)+\sqrt{n-2}+\sqrt{n-1}+\sqrt{n}$

……………………………………………………………………………………………………………….

$T(n)=T(1)+\sqrt{2}+............+\sqrt{n-2}+\sqrt{n-1}+\sqrt{n}$

$T(n)=T(0)+\sqrt{1}+\sqrt{2}+............+\sqrt{n-2}+\sqrt{n-1}+\sqrt{n}$

$T(n)=\sqrt{1}+\sqrt{2}+............+\sqrt{n-2}+\sqrt{n-1}+\sqrt{n}$  as $T(0)=0$

Now this summation we can write like ,

$T(n)=\sum_{i=1}^{n}\sqrt{n}$ which is approximately can be written

$\sum_{i=1}^{n}\sqrt{n}$ $\approx$ $\int_{1}^{n}\sqrt{x} dx$

$\large \int_{1}^{n}\sqrt{x} dx$

=$\large \frac{2}{3}\left [ n^{\frac{3}{2}}-1 \right ]$

So,$T(n)$ can be closely approximate to $\large n^{\frac{3}{2}}$.

So, $\large T(n)=\Theta (n^{\frac{3}{2}})$ .
edited by