What is an easy way for finding C and N when proving the Big

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

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

Say, for example:

(n+1)5, or n5+5n4+10n2+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 N0 >= 1 such that f(n) <= cg(n) for every integer N > N0.

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

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

---

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

| n5 + 5n4 + 0n3 + 10n2 + 5n1 + 1n0 | <= | n5 + 5n5 + 0n5 + 10n5 + 5n5 + 1n5 |

and you can simplify both sides to get

| n5 + 5n4 + 10n2 + 5n + 1 | <= | 22n5 |

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 N0, but this method works, and you can do it in your head.

(The absolute value operations around the polynomials are to account for negative coefficients.)

---

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 n3 + n is O(n3) you do the following:

(n3 + n) / n3 = 1 + (n / n3) = 1 + (1 / n2) < 2 for any n >= 1. Here you can pick any C >= 2 with No = 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.

链接地址: http://www.djcxy.com/p/39730.html

上一篇: 大O符号的帮助

下一篇: 在证明Big时找到C和N是一种简单的方法