Question

Let f(n) and g(n) be functions with domain {1, 2, 3, . . .}. Prove the following:
If f(n) = Ω(g(n)), then g(n) = O(f(n)).

Answer 1

Answer on Question #62636 – Math – Algorithms | Quantitative Methods

Question

Let $f(n)$ and $g(n)$ be functions with domain $\{1, 2, 3, \ldots\}$.

Prove the following:

If $f(n) = \Omega(g(n))$, then $g(n) = O(f(n))$.

Solution

If $f(n) = \Omega(g(n))$, then, by definition of $\Omega$, there exist positive constants $c$ and $n_0$ such that

$$c | g (n) | \leq | f (n) | \text{ for all } n \geq n_0.$$

Hence,

$$| g (n) | \leq \frac{| f (n) |}{c}.$$

Set

$$\frac {1}{c} = k.$$

If $c > 0$, then $k > 0$.

Besides,

$$| g (n) | \leq k | f (n) |.$$

Therefore, there exist positive constants $k$ and $n_0$ such that $|g(n)| \leq k |f(n)|$ for all $n \geq n_0$.

By definition of $O$,

$$g (n) = O (f (n)).$$

www.AssignmentExpert.com