Big-O of Set of Functions

50 Views Asked by At

I'm a bit puzzled on how to understand a bound.

We have two functions $f$ and $g$ such that

$$ f(n) = n^2 - n + 2 $$

and

$$ g(n) = 4n^2 +3n +2 $$

If we try to see if $f = O(g)$, we use the limit definition:

$$ \lim_{n \to \infty} \frac{n^2 - n + 2}{4n^2 + 3n + 2} $$ $$ = \lim_{n \to \infty} \frac{2n -1}{8n + 2} $$ $$ = \lim_{n \to \infty} \frac28 = \frac14 $$

Where, when graphed, $\frac14 (g)$ is an upper bound of $f$.

When we try to see if $f = \Omega(g)$, this is the result:

$$ \lim_{n \to \infty} \frac{4n^2 + 3n + 2}{n^2 - n + 2} $$ $$ = \lim_{n \to \infty} \frac41 = 4 $$

When graphed, $4(g)$ is not a lower bound of $f$. By the definition of big-$\Omega$, $f(n) \geq c \cdot g(n)$ for some $c \geq 0$, $\lim_{n \to \infty}\frac{g(n)}{f(n)} = c $.

1

There are 1 best solutions below

7
On BEST ANSWER

That last statement about $c$ is false. For your specific case you can pick $c = \frac14 - \varepsilon$ for any $\varepsilon > 0$ to make the inequality work. It may be helpful to notice that any polynomial of degree at most $k$ is in $O(n^k)$ and any polynomial of degree at least $k$ is in $\Omega(n^k)$.

It could also help to settle the definitions of $O$ and $\Omega$:

$$f\in O(g) :\Leftrightarrow \exists C>0, N\in\mathbb N \text{ s.t. } \forall n\ge N: f(n) \le C\cdot g(n)\\ f\in \Omega(g) :\Leftrightarrow \exists c>0, N\in\mathbb N \text{ s.t. } \forall n\ge N: f(n) \ge c\cdot g(n)$$

So you always have the existence of some constant such that eventually $f$ will be bounded above (resp. below) by $c\cdot g$.