How to find $c$ and $n_0$ for Big-Oh questions

I understand the theory behind the definition of Big-Oh, but when I try a question, I don't get how you would find the $c$ and $n_0$ values.

For example: if $f(n) = n!$ and $g(n) = 2^n$, how would I go about finding the $c$ and $n_0$ values for $g(n) = O(f(n))$?

In general, you should first set up the inequality and then try to solve for $n$ in terms of $c$. Often, this won't be feasible - there may not be a way to analytically obtain a closed-form solution involving only $c$ and $n$. In such cases, you can usually massage the inequality down to something where solutions can be determined by inspection.

In this case, we can start with the inequality $2^n \leq cn!$. You should be able to convince yourself that this isn't going to be a super-clean solution for $n$ here. Instead, we can try to massage this into a form that can be reasoned about.

Both of these terms involve repeated multiplication; we can write them out like that and see whether we notice a trick: $2 \times 2 \times ... \times 2 \leq c \times 1 \times 2 \times ... \times n$. We notice that the LHS is a product of $n$ terms, and the RHS consists of $c$ multiplied by $n$ other terms. Of the $n$ terms on the RHS besides $c$, all but $1$ are greater than or equal to the corresponding term on the LHS. If we rewrite the RHS as $(c \times 1) \times 2 \times ... \times n$ and choose $c = 2$, we get $2 \times 2 \times 3 \times ... \times n$. All $n$ of these terms are greater than or equal to the corresponding terms on the LHS, meaning the product is bigger, as we wanted. Thus, the choice $c = 2$ works for all choices of $n_0$.

Just to give you an idea of what a boring resolution would look like: let's show that $f(n) = 2n + 3$ is $O(g(n))$ if $g(n) = n + 1$.

We get $2n + 3 \leq c(n+1)$. Solving for $n$, we get $2n + 3 \leq c(n+1) = cn + c$, so $2n - cn \leq c - 3$ and $n(2 - c) \leq c - 3$. Note that if we choose $c \leq 2$, there are no valid solutions for $n$. We now have two cases: either $c \geq 2$ or $c < 2$. In the latter case, we can write $n \leq \frac{c-3}{2-c}$ which, along with the constraint that $n > 0$, yields no solutions. In the former case, we write $n \geq \frac{c-3}{2-c}$. You may now plug in any value of $c$ you like and find an $n_0$ to suit. We can see that the choice $c = 3$ allows us to choose $n_0 \geq 0$; the choice $c = 2.5$ requires that we choose $n_0 \geq 1$; etc.

If you're dealing with more complicated functions - specifically, ones that aren't monotonically increasing - you'll want to choose $n_0$ from the rightmost interval. Otherwise, the functions cross over each other again for a period, making your choice wrong. Usually, you don't have to worry about runtimes being other things than monotonically increasing, but it is a mathematical possibility of which you should be aware.

In this particular case, as $n$ increases by $1$, $g(n)$ doubles while $f(n)$ gets multiplied by $n+1$. That means that for $n \geq 1$, $g(n+1)/f(n+1) \leq g(n)/f(n)$, and so you can choose $n_0 \geq 0$ of your choice and $c = g(n)/f(n)$.

In the general case, suppose that you know that $g(n)/f(n) \to \gamma$, where $\gamma \neq \infty$. The proof of this should in principle give you a value of $n_0$ beyond which $g(n)/f(n) \leq \gamma+1$, say. One almost never has to do this sort of thing beyond introductory courses, so I can't offer any more general advice.

Remember that the answer is not unique and you don't need to find the minimal possible values of $c$ or $n_0$.

For example:

• $n!\geq\tfrac12\times2^n$ for all $n\geq 2$
• $n!\geq\tfrac34\times2^n$ for all $n\geq 3$
• $n!\geq1\times2^n$ for all $n\geq 4$
• $n!\geq2\times2^n$ for all $n\geq 5$

But, in this case, it's enough to observe that $2^n$ doubles each time $n$ increases, whereas $n!$ goes up by a factor of $n$ each time $n$ increases. Therefore, if you can find any $n_0\geq 1$ and any $c$ for which $n_0!>2^{n_0}$, then $n!>c.2^n$ for any $n>n_0$. For example, $1! > \tfrac1{1\,000\,000}2^1$, so you can take $n_0=1$ and $c=\tfrac1{1\,000\,000}$.

Usually, though, we just use standard facts, such as $p(n)=O(e(n))$ if $p$ is a polynomial and $e$ an exponential. Many of these facts and some techniques for proving them are in the answers to our reference question on Landau notation.