1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Hey @thomas, thanks for your detailed explanation and thought! $\endgroup$ – Yu-Hsiang Lin Oct 17 '16 at 14:54
  • $\begingroup$ (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. $\endgroup$ – Yu-Hsiang Lin Oct 17 '16 at 14:57
  • $\begingroup$ @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)$. $\endgroup$ – Thomas Klimpel Oct 17 '16 at 16:11
  • 1
    $\begingroup$ 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. $\endgroup$ – Yu-Hsiang Lin Oct 18 '16 at 9:56
0
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – Yu-Hsiang Lin Oct 18 '16 at 9:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.