From integral to $ \Theta\left(\sqrt{n}\left(\log{n} +1\right)\right)$

44 Views Asked by At

Why is $T_2(n) \in \Theta\left(n^{1/2}\left(1 + \int_1^{n}\frac{\sqrt{u}}{u^{1/2+1}}du\right)\right) \implies \Theta\left(\sqrt{n}\left(\log{n} +1\right)\right)$

I know that $n^{\frac{1}{2}} = \sqrt{n}$, but how does one get from the integral to log $n$ + 1?

And I know that $\Theta\left(\sqrt{n}\left(\log{n} +1\right)\right)$ = $\Theta(\sqrt{n} \log{n})$

1

There are 1 best solutions below

0
On BEST ANSWER

It looks like the term inside the integral equals $\frac{1}{u}$ as $u^{1/2}=\sqrt{u}$.

Hence it follows because $\log(u)$ is the anti-derivative of $\frac{1}{u}$.