Asymptotic Bound

45 Views Asked by At

$$T(n) = \Theta \left ( n^{1/2} \left ( 1 + \int_1^n \frac{1}{u^{3/2}}\ du \right ) \right ) = \Theta \left ( n^{1/2} \right )$$

This asymptotic bound is evaluated to be $n^{1/2}$ but isn't the correct answer $n$ and not $n^{1/2}$?

Just to give some background this is applying Akra and Bazi theorem on divide and conquer recurrence T(n).

1

There are 1 best solutions below

0
On BEST ANSWER

It looks like you may have a bit of an issue evaluating the integral.

$$\int_1^n \frac{1}{u^{3/2}} du = -\frac{2}{u^{1/2}} \bigg |_{u=1}^n = 2-\frac{2}{n^{1/2}}$$ Using this we can simplify $$n^{1/2} \left (1 + \int_{1}^n \frac{1}{u^{3/2}} du \right ) = n^{1/2}\left (3 - \frac{2}{n^{1/2}}\right ) = 3n^{1/2} - 2$$ When written in this form it is clear that the correct order is $\Theta(n^{1/2})$ since $$ \lim_{n\rightarrow \infty} \frac{3n^{1/2} - 2}{n^{1/2}} = 3 $$ which shows that for large enough $n$, the expression is within a constant multiple of $n^{1/2}$.