1
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.