10th Week - Nov 14th

Hey, this is week- ten lecture, which is also the last second lecture before final exam. During this week’s lecture, the ideas of “Big-Omega, big-Theta and general properties” were introduced.

As far as I am concerned, proofs are still the key concepts. Not only the lecture but also the tutorial emphasizes proving a problem by using big-Omega and big-Theta this week. One typical example would be prove 5n^4-3n^2+1 ϵ O (6n^5-4n^3+2n). To solve this question, we need to do a draft sketch to see what is the meeting point between those two functions. Therefore, (6n^5-4n^3+2n) need to be eliminated and 5n^4-3n^2+1 should be introduced. By eliminating (6n^5-4n^3+2n), simply removing the positive terms in this function, which leads to (6n^5-4n^3). And we times 4n^3 by n^2, which makes the function to become 6n^5-4n^5 = 2n^5. Since n>=1, we know 2n^5 > n^5. Vise visa, we introduce (5n^4-3n^2+1) by removing its negative term, which results to (5n^4+1). Multiplying (5n^4+1) by n^4 since n>=1, getting 6n^4. Similarly, we can get n*n^4 = n^5 >=6n^4 if we assume n>=6. After the above preparation, we spot that ‘n^5’ is the meeting point of two functions.

Kay, now it’s time to write down the proof. We can tell that this is a case of universal quantifier since by writing in symbolic form, the question would be like ∃c ϵ R+, ∃B ϵN, ∀n ϵ N, n>=B => 5n^4-3n^2+1 ϵ O (6n^5-4n^3+2n). Therefore, assuming n ϵ N, and n >= 6 is the first step of this proof. Then it comes the mathematic equations we did before as the draft sketch. Following that, we reintroduce ∀n ϵ N, n>=6 => 5n^4-3n^2+1 <= O (6n^5-4n^3+2n) and state the whole conditions as “ Then ∃c ϵ R+, ∃B ϵN, ∀n ϵ N, n>=B => 5n^4-3n^2+1 ϵ C <= (6n^5-4n^3+2n)”. However, this is one thing we need to notice is that we should remark ‘Pick C=1, B=6’, otherwise, the above proof would not make sense. Finally, we can come with the conclusion that 5n^4-3n^2+1 ϵ O (6n^5-4n^3+2n) by definition.

Personally I think, the “Big-Oh” proof is not that difficulty. There is nothing to worry about as long as you do the calculation before ahead correctly and follow the structures well.