World's most popular travel blog for travel bloggers.

[Answers] How to deal with $n\sqrt n$ in master theorem?

, , No Comments
Problem Detail: 

In classifying the following formula's asymptotic complexity using master theorem, I have $a = 8$, $b = 4$, and $d = ?$

$T(n) = 8T(n/4) + n\sqrt n$

How do I handle $n\sqrt n$ in this case to get $d$ ?

Asked By : ThisClark

Answered By : Luke Mathieson

You have to remember that $\sqrt[x]{y} = y^{\frac{1}{x}}$.

Then the rest should follow easily.

Don't look at the following unless you're genuinely stuck.

$n\sqrt{n} = n^{1}\cdot n^{\frac{1}{2}} = n ^{\frac{3}{2}}$, hence $d = \frac{3}{2}$. We also have $a = 8$ and $b = 4$, so $\log_{b}(a) = \log_{4}(8) = \frac{3}{2}$. Hence we have the second case of the Master Theorem where $f(n) \in \Theta(n^{d}\log^{0}n) = \Theta(n^{d})$ with $d = \log_{b}(a)$. Therefore $T(n) \in \Theta(n^{d}\log n) = \Theta(n^{\frac{3}{2}}\log n)$.

Best Answer from StackOverflow

Question Source :

3.2K people like this

 Download Related Notes/Documents


Post a Comment

Let us know your responses and feedback