Prove or disprove the bound given the recurrence relation
Your recurrence relation is covered by case 3 of the master theorem:


  If
  
  
  $T(n)=aT(\frac{n}{b})+f(n)$ where $a\geq 1$ and $b&gt;1$
  $f(n)\in\Omega(n^c)$ where $c&gt;\log_b a$
  $af(\frac{n}{b}) \leq k f(n)$ for some constant $k&lt;1$ and sufficiently large $n$
  
  
  then $T(n)\in \Theta(f(n))$


Note that $T(n)\in \Theta(f(n))$ means that both $T(n)\in O(f(n))$ and $f(n)\in O(T(n))$. So $T(n)\in O(f(n))$ follows from $T(n)\in \Theta(f(n))$.

In your case, you have $a=b=2$ and $f(n)\in\Omega(n^2)$ where $2 &gt;\log_2 2 = 1$. The only problem is that you cannot guarantee $2f(\frac{n}{2})\leq kf(n)$ for some constant $k&lt;1$ and sufficiently large $n$.

So you can disprove $T(n)=O(f(n))$ by a counterexample like $f(n)=n^2+\exp(n)\cos^2(\frac{\pi}{2}\log_2 n)$. Not really a great example for a nice exercise, but OK.