How to quickly determine running time of such recurrence relations?

Question

$$T(n)=5T(\frac{n}{2})+n\log n$$ $$T(n)=9T(\frac{n}{3})+n^2$$ $$T(n)=2T(\frac{2n}{3})+n^{1.5}$$

What are the running times of each $T(n)$? Each one looks like the form of the Master Theorem, but only the second one actually applies. For example, if we take the first $T(n)$: $T(n)=5T(\frac{n}{2})+n\log n$ so $a = 5, b = 2, c = 1,$ and $k=1$, but $c \not = \log_2 5$, so we can't use the master theorem here. Similarly for the third recurrence. For the second recurrence I found that $T(n)=\Theta(n^2)$, but I need methods to quickly solve the other two in an exam-type setting.

Answer 1

Actually, we can apply the Master Theorem to each recurrence relation.

1. Note that $a = 5$, $b = 2$, and $f(n) = n \log n$. Now recall that $\log n = O(n^\delta)$ for any $\delta > 0$ and that: $$ \log_b a = \log_2 5 > \log_2 4 = 2 > 1 $$ Hence, $f(n) = O(n^{\log_b a - \epsilon})$ if $0 < \epsilon < \log_2 5 - 1$. Thus, by Case $1$ of the Master Theorem, it follows that $T(n) = \Theta(n^{\log_b a}) = \Theta(n^{\log_2 5})$.

2. Note that $a = 9$, $b = 3$, and $f(n) = n^2$. Now since $\log_b a = \log_3 9 = 2$, it follows that $f(n) = \Theta(n^{\log_b a})$. Thus, by Case $2$ of the Master Theorem, it follows that $T(n) = \Theta(n^{\log_b a}\log n) = \Theta(n^2\log n)$.

3. Note that $a = 2$, $b = 3/2$, and $f(n) = n^{3/2}$. Now since: $$ \log_b a = \log_{3/2} 2 = \log_{3/2} 4^{1/2} = \frac{1}{2} \log_{3/2}(32/8) > \frac{1}{2} \log_{3/2}(27/8) = \frac{3}{2} $$ it follows that $f(n) = O(n^{\log_b a - \epsilon})$ if $0 < \epsilon \leq \log_{3/2} 2 - 3/2$. Thus, by Case $1$ of the Master Theorem, it follows that $T(n) = \Theta(n^{\log_b a}) = \Theta(n^{\log_{3/2} 2})$.