Prove or disprove the bound given the recurrence relation

Question

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.

Answer 1

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.

Answer 2

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.