Week 9 [Big-O Proof]

Let's review the definition of O(n^2) : a function f(n) is in O(n^2) iff there exists c in R+, there exists B in N, such that for all n in N, n>=B then f(n) <= c(n^2). From the definition we can find that for big-Oh proof, the most important part is about picking c and B. So here comes the question, how to pick c and B.

First example we talked in class is to prove 3n^2+2n ∈ O(n^2). There are two tips: tip 1: c should probably be larger than 3 (the constant factor of the highest-order term); tip 2: see what happens when n = 1=> 3n^2+2n=3+2=5=5n^2 so pick c=5 with B=1 is probably good. What happen when we add a constant? For example to prove 3n^2+2n+5 ∈ O(n^2). Same thing tip 1: c should be larger than 3; tip 2 see what happens when n =1=> 3n^2+2n+5=3+2+5=10=10n^2 so pick c=10 with B=1 is probably good.

After that we talked about a more complex example: to prove 7n^6 - 5n^4 +2n^3∈ O(6n^8-4n^5+n^2). The thinking process is:
                            6n^8-4n^5+n^2
--> assume n>=1       6n^8-4n^5
--> upper-bound         6n^8-4n^58 = 2n^8
the left side by overestimating
--> lower-bound        9n^6  <= 9/2 *(2n^8)
the right side by underestimating  7n^6 +2n^6 =9n^6
--> choose a c that connects the two bounds 7n^6 +2n^3
                                                                       7n^6 -5n^4+2n^3
The proof structure looks like:

Larry also talked about an example which is to prove n^3 O(3n^2). The process is to negate the definition first and then prove the negation.

The key is to figure out c and B. In general, larger c or larger B are good. These two examples are polynomials. How about non-polynomials? We use limit to prove it. The intuition is that if the ratio f(n)/g(n) approaches infinity when n becomes larger and larger that means f(n) grows faster than g(n).