Applying the master theorem

Question

State the asymptotic runtime found by the master theorem. If the master theorem does not apply state why:

1) $T(n) = $T($n/3)$

2) $T(n)= $ $5T$($2n/5$) + $n$

3) $T(n) = 4T(n/2) +15n^3 + 4n^2 +n+4$

1) For the first one I think the master theorem does not apply because I do not have a k-value, is this enough to show that I can't use the master theorem?

2) For the second one I know $a = 5 , b=2/5, k = 1$, so $log_\frac{2}{5}5$ < 1 , so the complexity would be O(n)

3) I don't know how to do can someone show me?

Can you guys verify whether my answers for 1 and 2 hold true and if possible show me how to deal with 3)?

Thank you

Answer 1

If will use the variable names from the Wikipedia page on the Master theorem.

1. $a = 1$, $b = 3$, so $\log_b(a) = 0$. But since $f(n) = 0$ it is also $f(n) \in O(n^{-1})$, so $c = -1$.
   Then $c < \log_b(a)$ and $T \in \Theta(n^0) = \Theta(1)$, which should be obvious as $T(n) = T(0)$ for any n.

2. $a$ and $c$ (or $k$) are correct but $b = 2.5$. So $T \in \Theta(n^{1.76})$.

3. $a = 4$, $b = 2$, $\log_b(a) = 2$, $f(n) \in \Omega(n^3)$.
   So $T \in \Theta(n^3)$.