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?
Best Answer
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?