Solving recurrences with Master theorem

86 Views Asked by At

Normally, the way I am solving those problems is the following: $3T(\frac{n}{2})+ n^4$

$a=3 ; b = 2 ; d=4$

then I am doing $\log(b(a))$ which is $log(2(3))= 0.6$

Since $0.6 < d$ I can apply the 1st case of the Master Therom which is $n^d$

My issue right now is I have to solve $T(n) = 2T (\frac{n}{4}) + (\sqrt n)$

So what is $d$ in that case? Normally $d$ is the power of $n$ but here we just have a $square$. Thank you

2

There are 2 best solutions below

2
On

$$\log_ba=\log_42=1/2\implies f(n)=\sqrt n\in\Theta(n^{\log_ba})$$Thus, by the Master Theorem, $T(n)\in\Theta(\sqrt n\log n)$.

2
On

We know master's theorem as $$T(n)=aT(\frac{n}{b})+\Theta(n^k \log ^p n)$$

Comparing this with your question $T(n) = 2T (\frac{n}{4}) + (\sqrt n)$, we get $a=2, b=4,p=0,k=\frac{1}{2}$.

$a=\bf{2} ~~\& ~~ b^k = 4^{1/2}=\bf{2}$

$\because a=b^k ~~ \& ~~ p> -1$, we have $$T(n)=\Theta(n^{\log_ba}\log^{p+1}n)$$ Substitting the values we get, $$\Theta(n^{\log_42}log^1n)=\Theta(n^{\frac{1}{2}\log_22}log^1n)= \boxed{\Theta(\sqrt(n)\log n)}$$


For your supplementary question about $T(n-2)$ you should check this