Using the master theorem/master method when $f(n) = 0$

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?

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

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.

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)})$.

• 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.
– kas
Sep 14 '17 at 19:36
• 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. Sep 14 '17 at 20:09
• 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)})$
– kas
Sep 14 '17 at 20:23
• 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. Sep 14 '17 at 22:58
• Ok, that makes sense now. Thanks again for walking me through this.
– kas
Sep 15 '17 at 15:29