1
$\begingroup$

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

$\endgroup$
5
  • 1
    $\begingroup$ 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}$. $\endgroup$
    – ttnick
    Commented Sep 27, 2022 at 7:23
  • $\begingroup$ @ttnick I still don't get it. $\endgroup$
    – Mina
    Commented Sep 27, 2022 at 7:35
  • $\begingroup$ Its because $O(n^{(log_ba) - \epsilon})$ is not the same as $O(n^{log_ba})$ $\endgroup$
    – Rinkesh P
    Commented Sep 27, 2022 at 8:01
  • 1
    $\begingroup$ You could write $f(n)=o(n^{\log_ba})$. $\endgroup$
    – user16034
    Commented Sep 27, 2022 at 9:35
  • $\begingroup$ @YvesDaoust That might be misleading. $\endgroup$
    – John L.
    Commented Oct 5, 2022 at 2:11

1 Answer 1

3
$\begingroup$

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.

$\endgroup$
0

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.