0

How do I prove the following?

$$O(n+\log(n)) \subset O(n \cdot \log(n))$$

I've plotted both functions and I see that $n+\log(n)$ is below $n \cdot \log(n)$. Can limit help me here?

$$\lim_{n \to \infty}\frac{n+\log(n)}{n \cdot \log(n)} = 0$$

If so, how does the limit imply that one set of functions is a subset of the other one? Can it be derived from the definition of $O$?

I've seen peoply try to prove the original statement by proving:

$$n+\log(n) \in O(n \cdot \log(n))$$

But that seems like saying $\{1, 2\} \subset \{2, 3\}$ because $2 \in \{1, 2\} \land 2 \in \{2, 3\}$ which is obviously wrong.

From the definition of $O$, it seems like I need to prove:

$$\forall n \in \mathbb{N}, \exists n_0 \in \mathbb{N}, \forall c_1 \in \mathbb{R}^+, \exists c_2 \in \mathbb{R}^+:\\n \geq n_0 \Rightarrow 0 \leq c_1 \cdot (n + \log(n)) \leq c_2 \cdot (n \cdot \log(n))$$

Does it make sense or is there simpler solution to this? Thanks.

1 Answers1

0

The following conditions are equivalent as $n\to\infty$:

  1. $O(n+\log(n)) \subset O(n \cdot \log(n))$;
  2. $n+\log(n)\in O(n \cdot \log(n))$;
  3. $\frac{n+\log(n)}{n \cdot \log(n)}$ is bounded;

Note that (3) clearly follows from $$\frac{n+\log(n)}{n \cdot \log(n)}=\frac 1n+\frac 1{\log(n)}\to 0 $$ as $n\to\infty$, hence all three statement above holds.

The only non trivial implication is $(2\Rightarrow 1)$ which follows from transitivity of the ordering on $\Bbb R$. For if $n+\log(n)\in O(n \cdot \log(n))$ then there exists a constant $C>0$ such that $n+\log(n)\leq C(n \cdot \log(n))$ eventually, and $f(n)\in O(n+\log(n))$ if and only if $f(n)\leq C'(n+\log(n))$ eventually for some constant $C'>0$. Thus, by transitivity, $f(n)\leq CC'(n \cdot \log(n))$ eventually thus proving $f(n)\in O(n \cdot \log(n))$.

In general, for eventually positive sequences $f,g:\Bbb N\to\Bbb R$ the following conditions are equivalent as $n\to\infty$:

  1. $O(f(n))\subseteq O(g(n))$;
  2. $f(n)\in O(g(n))$;
  3. $\frac{f(n)}{g(n)}$ is bounded;
Fabio Lucchini
  • 16,054