# Prove or disprove the bound given the recurrence relation

Given the following recurrence relation,

$T(n) = 2 T(\frac{n}{2}) + f(n)$,

where $f(n) = \Omega(n^2)$, I'm asked to prove or disprove that $T(n) = O(f(n))$.

If I'm allowed to restrict my discussion within the special cases in which that $n = 2^k$ for positive integer $k$, how can I prove or disprove the proposed bound, $T(n) = O(f(n))$?

As a side information, if $f(n) = \Theta(n^2)$, then we can show that $T(n) = \Theta(f(n))$ by the Master Theorem. But how should I handle the subtlety of this case with big-Omega and big-O?

Thanks for the help.

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>1$
• $f(n)\in\Omega(n^c)$ where $c>\log_b a$
• $af(\frac{n}{b}) \leq k f(n)$ for some constant $k<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 >\log_2 2 = 1$. The only problem is that you cannot guarantee $2f(\frac{n}{2})\leq kf(n)$ for some constant $k<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.

• Hey @thomas, thanks for your detailed explanation and thought! – Yu-Hsiang Lin Oct 17 '16 at 14:54
• (Sorry that I pressed return before I finished.) @thomas I actually checked your example (the cosine squared) and found that in that case $T(n)$ IS actually $O(f(n)) = O(n^2)$. I will give my thought in the next answer. But thanks and let me know if I misunderstood you or was wrong. – Yu-Hsiang Lin Oct 17 '16 at 14:57
• @Yu-HsiangLin Upss, forgot to multiply a fast growing function with the cosine squared. The point is that the $2T(n/2)$ part will make $T(n)$ significantly different from $f(n)$, because $f(n/2)$ can happen to be much bigger than $f(n)$. – Thomas Klimpel Oct 17 '16 at 16:11
• Thanks! Actually I just realized a fact very similar to your point. Simply put, if "$f(n)$ and $f(n/2)$ is significantly different" (it's a loose way of saying---I actually mean that $f(n = 2^k)$ evolves differently for even and odd $k$'s), then $T(n)$ is not bounded from below by $f(n)$ any more. – Yu-Hsiang Lin Oct 18 '16 at 9:56

Although we only know $f(n) = \Omega(n^2)$, let's consider this: if it turns out that $f(n)$ is actually $\Theta(n^{\alpha})$ for some $\alpha > 2$, then from the analysis similar to that of the Master Theorem (e.g. by recurrence tree) we can show that

$T(n) = \Theta(n) + g(n)$,

where

$g(n) = \displaystyle{\sum_{j=0}^{N-1}} \; 2^j \; f\left(\frac{n}{2^j}\right) \\ \quad\;\; = \Theta\left( \displaystyle{\sum_{j=0}^{N-1}} \; 2^j \; \frac{n^{\alpha}}{2^{\alpha j}} \right) = \Theta(n^{\alpha}).$

(One can show that this is true for all $\alpha > 1$.) Then we have

$T(n) = \Theta(n) + \Theta(n^{\alpha}) = \Theta(n^{\alpha})$,

since in our case $\alpha > 2$. And therefore we do have $T(n) = O(f(n))$.

My point is: for $f(n) = \Omega(n^2)$, the recurrence procedure is actually dominated by $f(n)$ during splitting/merging.

• As my reply to @thomas, if $f(n=2^k)$ evolves differently for even and odd $k$'s, then $T(n)$ cannot be described as "bounded from below by $f(n)$" any more. – Yu-Hsiang Lin Oct 18 '16 at 9:59