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$
0

2 Answers 2

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$
4
  • $\begingroup$ Hey @thomas, thanks for your detailed explanation and thought! $\endgroup$ Commented Oct 17, 2016 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$ Commented Oct 17, 2016 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$ Commented Oct 17, 2016 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$ Commented Oct 18, 2016 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
  • 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$ Commented Oct 18, 2016 at 9:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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