Question about $O$

16 Views Asked by At

Consider two non-negative sequences $f(n)$ and $g(n)$ and suppose that $\exists C>0, \ \forall \varepsilon >0, \exists N \in \mathbb{N}$ s.t. $$\forall n \geq N, \ \ f(n)<C \cdot g(n)+n^{\varepsilon}\varepsilon .$$ Is it true to say that arbitrariness of $\varepsilon$ implies $$\forall n \geq N, \ \ f(n) \leq C \cdot g(n),$$ and conserquently $$f(n)=O(g(n)) \ \ \text{as} \ n \to \infty?$$

1

There are 1 best solutions below

5
On

Example. $g(n) = 1$ and $f(n) = \log(n)$, $C=1$. Then we have:
for every $\varepsilon>0$ there exists $N>0$ such that $$\forall n \geq N, \ \ f(n)<C \cdot g(n)+n^{\varepsilon}\varepsilon$$ But $f(n) = O(g(n))$ fails.

added

For every $\varepsilon>0$ there exists $N>0$ such that $$\forall n \geq N, \ \ \log n < n^{-2}+n^{\varepsilon}\varepsilon$$ But $\log n = O(n^{-2})$ fails.