# Why not $O(n^{\log_ba})$ for case 1 of the Master Theorem instead of $O(n^{(\log_ba) - \epsilon})$?

Someone who was explaining to me the master theorem said that for the case 1, we compare the $$n^{\log_b(a)}$$ and $$f(n)$$. If the growth rate of $$n^{\log_b(a)}$$ is greater than the growth rate of $$f(n)$$ then we subtract an epsilon to have this equality: $$f(n) = O(n^{(\log_ba) - \epsilon})$$

My question is, doesn't the notation $$O$$ say that $$n^{\log_ba}$$ is the upper bound of the $$f(n)$$? So why don't we just write $$f(n) = O(n^{\log_ba})$$

• The first statement ist stronger. Case 1 of the Master Theorem only applies if $f$ is significantly (i.e. by an order of $n^\varepsilon$) smaller than $n^{\log_b a}$. Commented Sep 27, 2022 at 7:23
• @ttnick I still don't get it.
– Mina
Commented Sep 27, 2022 at 7:35
• Its because $O(n^{(log_ba) - \epsilon})$ is not the same as $O(n^{log_ba})$ Commented Sep 27, 2022 at 8:01
• You could write $f(n)=o(n^{\log_ba})$.
– user16034
Commented Sep 27, 2022 at 9:35
• @YvesDaoust That might be misleading. Commented Oct 5, 2022 at 2:11

Good question.

Suppose we have a positive function $$T(n)$$ such that

$$T(n) = a \cdot T\left(\frac{n}{b}\right) + f(n)$$

with $$a \geq 1, b > 1$$. You are referring to case $$1$$ of the master theorem:

$$\qquad$$ If $$f \in O( n^{\log_b (a) - \epsilon})$$ for some $$\epsilon > 0$$, then $$T \in \Theta\left( n^{\log_b a} \right)$$.

(There are various versions of the master theorem. There is not much variation on the case $$1$$, though.)

#### Why don't we just write $$f(n) = O(n^{\log_ba})$$ as the antecedent for case $$1$$?

Because we cannot.

For example, consider $$T(n)=2T(\frac n2)+n$$.
So $$a=2$$, $$b=2$$, $$\log_ba=1$$, $$f(n)=n=O(n^1)$$. However, $$T(n)\not\in\Theta(n^1)$$.

In fact, $$T(n)\in \Theta(n\log n)$$. This $$T(n)$$ belongs to the situation with $$a=b=2, k=0$$ of the case $$2$$ of the master theorem:

$$\qquad$$ If $$f \in \Theta( n^{\log_b a} \log^{k} n)$$ for some $$k \geq 0$$, then $$T(n)\in \Theta( n^{\log_b a} \log^{k+1} n)$$.

#### Can we just write $$f(n)=o(n^{\log_ba})$$ as the antecedent for case $$1$$?

No, we cannot either.

For example, consider $$T(n)=2T(\frac n2)+n/\log n$$.
So $$a=2$$, $$b=2$$, $$\log_ba=1$$, $$f(n)=n/\log n\in o(n^1)$$. However, $$T(n)\not\in\Theta(n^1)$$.

In fact, applying Akra–Bazzi method, we have $$T(n)\in \Theta(n\log\log n)$$. See here for an easy explanation why $$T(n)\in \Theta(n\log\log n)$$.

#### So, $$O(n^{(\log_ba) - \epsilon})$$ for some $$\epsilon>0$$.

"Case $$1$$ of the master theorem only applies if $$f(n)$$ is significantly (i.e. by an order of $$n^ε$$ for some $$\epsilon>0$$) smaller than $$n^{\log_ba}$$", as ttnick remarked.