I am currently working on applications of the master theorem, where it came to pass that I failed to find a solution to a problem.
Given the recursion:
$T(n) = aT\left( \frac{n}{b} \right) + f(n)$
where $f(n)$ is a non-negative function of asymptotic growth $f(n) \in \theta \left( n^{\log_ba} \log n \right)$. Show that if $n = b^k, \, k \in \mathbb{N}$ then $T(n) \in \theta \left(n^{\log_b a} \log^2n\right)$.
(The $\log$ without any index is meant to be $\log_2$).
Now as far as I know, for such a recursive function the master theorem gives 3 possible cases:
- if $\quad f(n) \in O\left( n^{\log_b a - \varepsilon} \right) \quad$ for a $\, \varepsilon > 0 \,$, then $\quad T(n) \in \theta \left(n^{\log_b a}\right)$
- if $\quad f(n) \in \theta \left(n^{\log_b a}\right) \quad$ then $\quad T(n) \in \theta \left(n^{\log_b a} \log n\right)$
- if $\quad \exists \, 0<c<1 \, \, \, \exists \, n_0 \in \mathbb{N} \, \, \, \, \forall n \geq n_0 : a f(\frac{n}{b}) \leq c f(n) \quad$ then $\quad f(n) \in \Omega \left( n^{\log_b a + \varepsilon}\right) \quad$ and $T(n) \in \theta\left( f(n) \right)$
I just can't see, how to usefully apply masters theorem here. I'd appreciate advice or hints.
Octavius