0

I'm trying to solve two problems with Master theorem (quoted at the end of this post). I have solved them and found some answers, but I'm not sure whether my answers are right or not. Can you please check my answers and if they have any problem, explain for me?

Thank you so much.

$$T(n)=2T\left(\frac{n}2\right)+n\sqrt{\log n}$$

My answer, which I have found with Case 2 of Master theorem: $$\theta(\log^\frac{3}2n)$$

$$T(n)=T\left(\frac{2n}3\right)+\log^2n$$

My answer, which I have found with case 2 of Master theorem: $$T(n)=\theta(\log^3n)$$

Here's the statement of the Master theorem:

enter image description here

Blue
  • 75,673
anita
  • 33

1 Answers1

1

The first exercise is definitely solved wrongly. You have $T(n) = 2T(\frac{n}{2})+ n\sqrt{\log n}$ which implies $T(n) = \Omega(n \sqrt{\log n})$. Also case 2 is not suitable here, because $n \sqrt{\log n} = \Omega(n) = \Omega(n^{\log_2 2})$. Note that case 3 is also not applicable here, because $n \sqrt{\log n} = o(n^{1 + \varepsilon})$ for all $\varepsilon > 0$.

For the second exercise the Master theorem is also not applicable, because $\log_{2/3} 1 = 0$, and $f(n) = \Omega(1)$, and $\log^2 (2n/3) = \log^2 n + 2(\log n) \cdot (\log 2/3) + \log^2 2/3 \sim \log^2 n > cf(n)$ for each $c < 1$ and sufficiently large $n$.

Smylic
  • 6,715