Prove a function is in Big-Oh and not in Big-Omega

Question

We are told to use the definitions of Big-Oh and Big-Omega to prove that a given function is in $O(f(n))$ or $\Omega(f(n))$. It requires being able to use $c$ and $n_0$.

Use the definitions to show that $6n^2 + 20n \in O(n^3)$ but $6n^2 + 20n \not\in \Omega(n^3)$

The only way I know that these are true are by looking at the term with the highest power. For instance, we are looking at $O(n^3)$ which means that any function whose highest power is 3 or lower will be in $O(n^3)$. So in this case the highest term is an $n^2$ and $n^2 < n^3$ so that means $6n^2 + 20n \in O(n^3)$.

That's not the way to prove it though. We are supposed to use the definition that $T(N) \in O(f(N))$ if there exists positive constants $c$ and $n_0$ such that $T(N) \geq cf(n)$ when $N \geq n_0$ for Big-Oh and vice versa for Big-Omega.

How do I know which $c$ and $n_0$ to choose? Also, I am confused on where $n_0$ even comes into play. I mean, in the definition where it says a positive constant $c$ and $n_0$ exists, we use that $c$ value in the expression $T(N) \geq cf(n)$, but we don't use $n_0$ anywhere so why do we need it?

Answer 1

There is no choice of $c$ and $n_0$ that is "the correct" choice. If there is any correct choice, then there are many correct choices. A big-O or big-omega proof does not depend on making "the correct" choice, only on making a correct choice.

By the way, be more careful with the equations. The variable names $N$ and $n$ are not interchangeable, and the condition "$T(N) \geq cf(n)$ when $N \geq n_0$" is not a correct way to test big-O. A correct way to state the condition is, $T(N) \in O(f(N))$ if

$$ T(N) \leq cf(N) \text{ when } N \geq n_0$$

for some positive constants $c$ and $n_0$.

You can write this using different variables, but you must use the same variable name in three places: as the parameter of $T$, as the parameter of $f$, and as the number that is $n_0$ or greater. You can write $n$ instead of $N$, but you must then change all three $N$s to $n$. Also make sure you write $\leq$ for big-O, not $\geq$.

When the condition is written correctly, $n_0$ most certainly is used by the definition of big-O, though sometimes only in a trivial way (for example, sometimes $n_0 = 0$ is good enough).

Because $n^3$ grows so much "faster" than $6n^2 + 20n$, it is especially easy to show that $6n^2 + 20n \in O(n^3)$ using the definition of big-O. Try this: take a wild guess at a value of $c$. That's right, pick a number, any (positive) number. Now what can you say about $n$ if $6n^2 + 20n \leq cn^3$? Can you find any value to substitute for $n$ that makes this inequality true? If you have found such a value to substitute for $n$, what can you say about any larger value you could substitute for $n$?

Alternatively, let $n_0 = 0$. What can you say about $c$ if $n = 1$ and $6n^2 + 20n \leq cn^3$? Suppose you have some other value of $n$ instead, will that value of $c$ still make the inequality true? If not, how can you fix it?

Answer 2

This will not give you explicit constants, but is most likely one of the fastest ways to deal with such problems.

Note that the definition of $O(\cdot)$ you give is: $$ f(n) \in O(g(n) \text{ iff } \exists C> 0, n_0 \text{ s.t. } \forall n\geq n_0, \ f(n) \leq Cg(n). $$ Another way to see it is to rewrite (assuming $g(n)>0$ for $n$ big enough, which is "always" the case in analysis of algorithms, since typically $g$ is monotone increasing): $$ f(n) \in O(g(n) \text{ iff } \exists C> 0, n_0 \text{ s.t. } \forall n\geq n_0, \ \frac{f(n)}{g(n)} \leq C. $$ A stronger condition (which implies this) is to have $\left(\frac{f(n)}{g(n)}\right)_n$ being a convergent sequence, which converges to some $\ell \in\mathbb{R}$. Indeed, then this ensures that the sequence is bounded...

So we have the implication:

$\exists \ell\in\mathbb{R}\text{ s.t. }\frac{f(n)}{g(n)}\xrightarrow[n\to\infty]{}\ell$ implies $f(n) = O(g(n))$.

Similarly, we have

$\frac{f(n)}{g(n)}\xrightarrow[n\to\infty]{} 0 $ implies $f(n) = o(g(n))$

and

$\exists \ell > 0\text{ s.t. }\frac{f(n)}{g(n)}\xrightarrow[n\to\infty]{}\ell$ implies $f(n) = \Omega(g(n))$.

Applying it to your problem, we have $$ \frac{f(n)}{g(n)}=\frac{6n^2+20n}{n^3} \xrightarrow[n\to\infty]{} 0 $$ so that (i) we do have $f(n) \in O(g(n))$; but (ii) actually $f(n) \in o(g(n))$, which implies $f(n) \not\in \Omega(g(n))$.

Answer 3

The point of big-$O$ (and big-$\Theta$ and big-$\Omega$) notation is to make precise the notion of the rate of growth of a function. When we say $f = O(g)$ we mean that $f$ grows more slowly than $g$. In order to be useful this notion shouldn't really depend on constant multiples of the function, nor should it really depend on the behavior of the function at "early times". For instance, suppose that $f(x) = e^{x/10} - 5$. This function grows incredible quickly, being exponential, but is negative until about $x = 16$. It doesn't catch up to $g(x) = x^2$ until $x = 90$ or so, but it grows faster forever after. If you didn't have $n_0$ in this case, there would be no way to capture this intuitive fact about $f$'s relationship to $g$. The constant multiple won't help you since $f$ is negative for a while.

For your specific problem, you know that $x^n > x^k$ for $n > k$ so long as $x > 1$, so for the first problem $C = 26$ and $n_0 = 1$ work. For the second, divide $6x^2 + 20x$ through by $x^3$ and show that it cannot be bounded below by a constant, no matter how large $n_0$ you choose.

Answer 4

We use $n_0$ in the same condition: $T(N)\le c\cdot f(N)\ $ when $N\ge n_0$.

Since the definition only require existence, we can estimate roughly by choosing $c$ and $n_0$ as needed for the estimation to work.

So, for $6n^2+20n\in O(n^3)\ $ we need to have $6n^2+20n \le c\cdot n^3 $ for almost all $n$.

Well, in this particular case we are free to choose $c=26$, say, and then the condition will indeed hold for all $n$'s: $$6n^2+20n\le6n^3+20n^3=26n^3$$

However, we could have equally well chosen any smaller $c$. For, say $c=20$, the condition will hold only for $n>1$.

Answer 5

prove it by contradiction.

if we assume there exists a constant C such that

$$ 6n^2 + 20 n \ge C n^3 $$ for all n large

let $ n > \max\{20, 7/C\} + 1$ and so $$ 6n^2 + 20 n \lt 6 n^2 + n^2 = 7 n^2 = C* \frac{7}{C} n^2 \lt Cn^3$$ it ends to the contradiction.