Prove that for a function $f$, $o(f(n)) \subset O(f(n))$

101 Views Asked by At

Given a function $f$, prove the following: $$o(f(n)) \subset O(f(n))$$

I started by assuming that exists $h(n)$ that satisfies $h(n) \in o(f(n))$, by definition for every $c > 0$ there is $n_0 > 0$ such as: $$ h(n) \leq c \cdot f(n)$$

How can I continue? Notice that a subset is required and not a subset equal.

1

There are 1 best solutions below

0
On BEST ANSWER

Assuming all functions are non negative.

The definition of $h(n)\in o\left(f(n)\right)$ is

$$\forall C\gt 0, \exists N, n\geq N\Rightarrow h(n)\leq Nf(n)$$

The definition of $h(n)\in O\left(f(n)\right)$ is

$$\exists C\gt 0, \exists N, n\geq N\Rightarrow h(n)\leq Nf(n)$$

Can you take it from here ?

For the strict inclusion consider $f(n)=n+1$ and $h(n)=n$