0
$\begingroup$

I spent the last couple of days trying to understand the different asymptotic notations but it seems I'm hitting some conflicting information.

For context, I believe I've understood the formal definition of different notations, as they are fairly similar to the definition of limit I've learned before. It also seems to me that, in practice when people talk about $Big\;O$, they're most likely referring to $Big\;\Theta$ for the worse case (e.g., the discussion of $Big\; O$ in this CMU handout).

Here is what confuses me:

In this Reddit post, some commenters claimed that any function is $Big\;O$ / $Big\;\Theta$ / $Big\;\Omega$ of itself. I'm okay with this because it reflects the definition. However, this phrasing seems to imply that when we say $f(n) = O(g(n))$, $g(n)$ isn't necessarily of the 'clean' forms $n$, $log(n)$, or $n^2$. For example, using the above phrasing, it seems correct to say that $n^2 - 3n + 4 = O(n^2 - 3n + 4)$, which leads me to this explanation of little o on Wikipedia.

To summarize, it says:

$f(x) = o(g(x)$ as $x \to \infty$

if for every positive constant $ε$ there exists a constant $x_{0}$ such that

${\displaystyle |f(x)|\leq \varepsilon g(x)\quad {\text{ for all }}x\geq x_{0}.}$

Per this definition, it seems correct to say $f(n) = o(g(n))$ for $f(n) = n^2 - 3n + 4$ and $g(n) = 2n^2$ because $g(n) ≥ f(n)$ for $n ≥ 1$ for all positive values of $ε$.

However, the CMU handout linked above also has a section at the end that explains little o, where it says $f(n) = o(g(n))$ when $\lim\limits_{n \to \infty} \frac{f(n)}{g(n)} = 0$.

This seems incompatible with the example I gave above for Wikipedia's definition, because $\lim\limits_{n \to \infty} \frac{n^2 - 3n + 4}{2n^2} = \frac12$

How should I reconcile these two definitions?

Thank you very much!

$\endgroup$

1 Answer 1

1
$\begingroup$

The two definitions are equivalent and it is not true that $n^2 - 3n + 4 = o(2 \cdot n^2)$.

The arbitrary positive $\varepsilon$ in the definition is a real number, not just positive integer. For example for $\varepsilon = \frac14$ we do not have $n^2 - 3n + 4 \leq \varepsilon \cdot 2n^2$ for large enough $n$.

$\endgroup$
3
  • $\begingroup$ Hi, thank you! That makes sense now! I have another question. Is it correct to say that little o is just the set of Big O excluding Big Theta? $\endgroup$ Jan 2 at 6:22
  • 1
    $\begingroup$ Not in general. For example if we take $f(n) = \begin{cases}n, & \text{$n$ even} \\ 0, & \text{$n$ odd}\end{cases}$, then $f(n) = O(n)$, $f(n)$ is not $\Theta(n)$, and not in $o(n)$. $\endgroup$ Jan 2 at 6:26
  • $\begingroup$ Thank you so so much!! $\endgroup$ Jan 2 at 7:29

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.