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

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?

• $f=X(g)$ is equivalent to $f/g=X(1)$. Now, $o(1)$ are functions that converge to $0$. $O(1)$ are bounded functions. $\Omega(1)$ are functions bounded away from $0$. $\omega(1)$ are functions converging to $\infty$ and $\Theta(1)$ are functions bounded away from $0$ and $\infty$. $\sim 1$ are functions converging to $1$. – A.S. Feb 4 '16 at 23:07
• @A.S. That's basically what I tried to convey in my answer. I don't get why this is so seldom mentioned in Intro to Algorithms class: it simplifies a lot the task of dealing with asymptotic analysis (by reducing it, essentially, to checking convergence or boundedness of a sequence). – Clement C. Feb 4 '16 at 23:19
• @Clement Maybe because running time is more tangible than ratio of running times? While my presentation is good for deeper understanding/intuition, it's not that great for manipulations: $n^3+n^2\le 2n^3=O(n^3)$ is easier/more illustrative than looking at the ratio. Separately, I'll add for completeness that "bounded away from zero" means $\liminf >0$, not that the ratio never hits $0$. Same for bounded away from $\infty$. – A.S. Feb 4 '16 at 23:41
• @A.S. Indeed -- but in most practical purposes, $f,g$ are both functions monotonically increasing to $\infty$, so things go very nicely (and checking the limit is very often very simple.) – Clement C. Feb 4 '16 at 23:44

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?

• I think I understand what's going on now. As far as me typing $T(N) \geq cf(n)$ that was me typing too fast and not going back to check. So in order to show that some equation is in Big-Oh, I literally just pick any positive constant and some arbitrary $n_0$? So let's say that I pick $n_0$ to be 3. That means all values of $n$ that I plug into my equation will be greater than $3$? Or does that mean all values of $n$ that will make this inequality true have to be greater than $3$? – GenericUser01 Feb 4 '16 at 23:14
• In general it doesn't always work to start choosing arbitrary values of either $c$ or $n_0$. This just happens to be a very easy problem where you have an especially wide set of choices. Even so, once you choose either $c$ or $n_0$, you have to give some thought to choosing the other one; for example, $c=1, n_0=1$ clearly does not work, because $6n^2 + 20n \not\leq n^3$ if $n=1$. What I gave you was two ways to find the numbers you need for this particular problem, one way where you pick $c$ first, and another where you pick $n_0$ first. – David K Feb 4 '16 at 23:19
• So is $n_0$ some value we plug in? You said that if $c = 1, n_0 = 1$ then it wouldn't work. Would this work if say $c = 1, n_0 = 1000$? – GenericUser01 Feb 4 '16 at 23:22
• If we plug in $1000$ then we get $6,020,000 \leq 1,000,000,000$ which is true? – GenericUser01 Feb 4 '16 at 23:26
• Looks correct to me. What if we set $c=1, n_0 = 1000$, then? if $n \geq 1000$, is it necessarily true that $6n^2 + 20n \leq n^3$? (It is, but you might need to do a little algebra to prove it.) If you can get that to work then you've proved $O(n^3)$. There are smaller values of $n_0$ that would work but this one is just as "proofy" as any of them. – David K Feb 4 '16 at 23:30

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))$.

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.

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$.

• I am confused on how $6n^2 + 20n$ was suddenly turned into $6n^3 + 20n^3$. How come we just changed their values to get $26n^3$? – GenericUser01 Feb 4 '16 at 23:12
• That's a lazy but clear way for the proof. We used $n,\,n^2\le n^3$. That holds, doesn't it? So choose $n_0=0$ and $c=26$ and that proves. (Actually, we also have $6n^2+20n\in o(n^3)$ where this cheap trick won't solve it..) – Berci Feb 4 '16 at 23:14
• I understand that $n, n^2 \leq n^3$, but I don't understand why that means we can just change their values to $6n^2$ to $6n^3$. – GenericUser01 Feb 4 '16 at 23:16
• The change you probably have in mind would be denoted by an = sign. Here we used $\le$. Well, that's an estimating. – Berci Feb 4 '16 at 23:17
• I am still confused. I just don't get why we need to "change" or whatever to make both terms in that equation have an $n^3$. – GenericUser01 Feb 4 '16 at 23:19

$$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.