Problems showing the constraint of master theorem case three holds Prove or disprove the following statements:


$T\left( n \right) = 2T\left( {\frac{n}{2}} \right) + f\left( n \right),f\left( n \right) = \theta \left( {{n^2}} \right) $ then $ {\rm{ }}T\left( n \right) = \theta \left( {f\left( n \right)} \right) $ for all $ {\rm{ n = }}{{\rm{2}}^k}$
$T\left( n \right) = 2T\left( {\frac{n}{2}} \right) + f\left( n \right),f\left( n \right) = \Omega \left( {{n^2}} \right) $ then $ {\rm{ }}T\left( n \right) = O\left( {f\left( n \right)} \right)$ for all $ {\rm{ n = }}{{\rm{2}}^k}$


I think I should use the third case of the master theorem to check these equations.

But I have not been able to check this constraint for these inequations:

$\qquad af\left( {\frac{n}{b}} \right) \le cf\left( n \right)$

How do I do that?
The following shows that the second statement is false.

Define $f$ as follows:
$$ f(n) = \begin{cases} 4n^3 &amp; n \text{ is a power of }4, \\ n^2 &amp; \text{otherwise}. \end{cases} $$
Let $n = 2^{2k+1}$. Then $f(n) = n^2$ while
$$ T(n) \geq 2T(n/2) \geq 2f(n/2) = n^3. $$