1
$\begingroup$

I'm trying to find a solution to the recurrence $T(n)=3T(\frac{n}{2})$ with the master theorem for divide-and-conquer recurrences, but I'm not sure which case I can apply since $f(n) = 0$.

If you can use the master theorem, I'm leaning towards $T(n)=\Theta(n^{\log_2{3}})$, since $0 \leq n^{\log_2{3}}$. But I'm hung up on a few particular definitions.

  1. Is it true that $0=O(n^{\log_2{3}})$? What would be the values of $c$ and $n_0$ such that $\exists c>0,n_0> 0:f(n) \leq cn^{\log_2{3}}, \forall n \geq n_0$?

  2. Is zero asymptotically smaller than $n^{\log_2{3}}$ by a factor of $n^\epsilon, \epsilon > 0$?

In general, I'm asking if lacking a $f(n)$ makes the master theorem not applicable and why?

$\endgroup$
3
  • $\begingroup$ What's the relation between $f$ and $T$? $\endgroup$ Sep 14 '17 at 19:17
  • $\begingroup$ $T(n) = aT(\frac{n}{b}) + f(n)$ $\endgroup$
    – kas
    Sep 14 '17 at 19:51
  • 1
    $\begingroup$ :-) Okay. (would rather have you mention that in the post) $\endgroup$ Sep 14 '17 at 19:53
2
$\begingroup$

I assume by $f(n)$, you mean your recurrence relation to be of the form $$ T(n)=aT\left(\frac{n}{b}\right)+f(n), $$ so that in this case you have $a=3$, $b=2$, and $f(n)=0$ for all $n$.

That being the case: yes, $f(n)=0$ is perfectly acceptable.

To answer your more specific questions:

  1. Yes, $0=O(n^{\log_2(3)})$. Take absolutely any $n_0\in\mathbb{N}$ and any $c>0$, and it is true that $0\leq cn^{\log_2(3)}$ for all $n\geq n_0$. Remember, Big-O just represents asymptotic upper bounds; of course something that goes to infinity is an upper bound, in the limit, for $0$.

  2. Yes, $0$ is 'asymptotically smaller' than $n^{\log_2(3)}$. Take absolutely any $\epsilon\in(0, \log_2(3))$, and it is true that $0=O(n^{\epsilon})$.

The Master Theorem is perfectly applicable in this situation, and it shows that your $T(n)$ satisfies $T(n)=\Theta(n^{\log_2(3)})$.

$\endgroup$
5
  • $\begingroup$ Thanks for your detail and quick response. For $0=O(n^{\log_2(3)})$ must we include zero in the set of natural numbers? The book I'm using for definitions (The CLRS Algorithms) says $c$ and $n$ are "positive constants," which I thought excluded zero. $\endgroup$
    – kas
    Sep 14 '17 at 19:36
  • $\begingroup$ I didn't choose either $c$ or $n$ to be $0$, so I'm not sure I follow your question. I chose $c$ to be any positive real, and $n$ to be any natural number. $\endgroup$ Sep 14 '17 at 20:09
  • $\begingroup$ I'm often wrong, but won't either $c$ or $n$ have to be zero so $0=cn^{\log_2(3)}$? Otherwise, $cn^{\log_2(3)}$ won't be a asymptotically tight bound for $f(n)$, and the best I could say for the original problem is that $f(n)=o(cn^{\log_2(3)})$ $\endgroup$
    – kas
    Sep 14 '17 at 20:23
  • $\begingroup$ You seem to be thinking of $\Theta$, not $O$. All that $0=O(n^{\log_2(3)})$ means is that for $n$ sufficiently large, we can bound $0\leq cn^{\log_2(3)}$. There is no requirement at all that the bound be asymptotically tight. $\endgroup$ Sep 14 '17 at 22:58
  • $\begingroup$ Ok, that makes sense now. Thanks again for walking me through this. $\endgroup$
    – kas
    Sep 15 '17 at 15:29

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.