Week 10: Test Two and Chapter Four

I thought chapter four is something easy before because I have been using big-Oh since grade ten. Today, I have changed my view. I saw it easy just because I can judge a program as O(n^2) if there is a double loop. However, everything will seem hard when we learn it in mathematical language. It is a rigorous method to prove something.

This week for chapter four, we did more on proving big-Oh and big-Omega. The point is still how to choose c and B. Basically, for polynomial functions, we can just choose B = 1, which is a magic breakpoint. Then we underestimate the larger side of the equation, and overestimate the other side. Finally, we can get f(n) >= c * g(n) or f(n) <= c * g(n). 

Overall, we are proving with specific numbers. What about more general things? First, we want to define the set of functions that we are doing so far. They are all like, input a natural number and output a positive real number. Then define their set as F:{f: N-->R+}. Now, we can prove general things by choosing functions from this set. The most important thing is still how to wisely choose c and B, which mostly related to other c's and B's.

Basically I'm (quite) happy that chapter four is over because it's the most difficult part so far. (Of course everything gets harder and harder.) Meanwhile, I delighted that I got 29 in test 2, which actually I think I deserved. 

My friend posted something that really enlightened me in this week's blog where he said that "when finding upper-bound, it is OK to over-estimate the number of steps" and "when finding lower-bound, it is OK to under-estimate the number of steps". Professor Heap might mentioned this during lecture, but I think I missed them. Anyway, these ideas teach us what to do when proving some function is in O(something). We can say n^2+2n+1>n^2 or n^10-n^6<n^10, which is how we prove them.