What is an easy way for finding C and N when proving the Big-Oh of an Algorithm?

Question

I'm starting to learn about Big-Oh notation.

What is an easy way for finding C and N₀ for a given function?

Say, for example:

(n+1)⁵, or n⁵+5n⁴+10n²+5n+1

I know the formal definition for Big-Oh is:

Let f(n) and g(n) be functions mapping nonnegative integers to real numbers. We say that f(n) is O(g(n)) if there is a real constant c > 0 and an integer constant N₀ >= 1 such that f(n) <= cg(n) for every integer N > N₀.

My question is, what is a good, sure-fire method for picking values for c and N₀?

For the given polynomial above (n+1)⁵, I have to show that it is O(n⁵). So, how should I pick my c and N₀ so that I can make the above definition true without guessing?

Answer 1

You can check what the lim abs(f(n)/g(n)) is when n->+infitity and that would give you the constant (g(n) is n^5 in your example, f(n) is (n+1)^5).

Note that the meaning of Big-O for x->+infinity is that if f(x) = O(g(x)), then f(x) "grows no faster than g(x)", so you just need to prove that lim abs(f(x)/g(x)) exists and is less than +infinity.

Answer 2

You can pick a constant c by adding the coefficients of each term in your polynomial. Since

| n⁵ + 5n⁴ + 0n³ + 10n² + 5n¹ + 1n⁰ | <= | n⁵ + 5n⁵ + 0n⁵ + 10n⁵ + 5n⁵ + 1n⁵ |

and you can simplify both sides to get

| n⁵ + 5n⁴ + 10n² + 5n + 1 | <= | 22n⁵ |

So c = 22, and this will always hold true for any n >= 1.

It's almost always possible to find a lower c by raising N₀, but this method works, and you can do it in your head.

Edit: I added absolute value operations around the polynomials to account for negative coefficients.

Answer 3

It's going to depend greatly on the function you are considering. However, for a given class of functions, you may be able to come up with an algorithm.

For instance, polynomials: if you set C to any value greater than the leading coefficient of the polynomial, then you can solve for N₀.

Answer 4

Usually the proof is done without picking concrete C and No. Instead of proving f(n) < C * g(n) you prove that f(n) / g(n) < C.

For example, to prove n³ + n is O(n³) you do the following:

(n³ + n) / n³ = 1 + (n / n³) = 1 + (1 / n²) < 2 for any n >= 1. Here you can pick any C >= 2 with No = 1.

Answer 5

After you understand the magic there, you should also get that big-O is a notation. It means that you do not have to look for these coefficients in every problem you solve, once you made sure you understood what's going on behind these letters. You should just operate the symbols according to the notaion, according to its rules.

There's no easy generic rule to determine actual values of N and c. You should recall your calculus knowledge to solve it.

The definition to big-O is entangled with definition of the limit. It makes c satisfy:

c > lim |f(n)/g(n)|, given n approaches +infinity.

If the sequence is upper-bounded, it always has a limit. If it's not, well, then f is not O(g). After you have picked concrete c, you will have no problem finding appropriate N.