Week 9: exercises of proving Big-Oh (using limit techniques)

This week is all about big-Oh proofs.

I like the graphic expression. In the picture on the left, point B is indicated as a break point, beyond which f(n) is upper-bounded by cn^2.

Note: remember noting that O（n^2）belongs to a set of functions

functions that take in natural numbers and return non-negative real numbers

For exercising, I want to pick the more complicated one from examples taught in class to analyze:

To prove

①negate

 then we have

②prove the negation 

③the hardest part: picking a wise n

Since we want both n≥3c and n≥B, we need more than "pick n=max(3c,B)". Instead, we pick n = max(floor of 3c, B)+ 1 because the value of floor of 3c is either 3c or (3c -1)by the definition of floor. Then (floor of 3c) +1 must ≥ 3c. 

④brainstorm finished. Now we only need to follow the proof structure write down the thoughts step by step, watching out indention errors. 

tips of using limits techniques to disprove big-Oh：

By proving limit, we can obtain either 2^n / n^2 ＞ c or 2^n / n^2 ＜ c depending on the value of the limit：

Then we can use the result to disprove big-Oh, since its result is f(n)≤c*g(n).