For this week, we learned about the big omega proof and the big oh proofs for general functions. Since big-Omega proofs were mostly similar to big-oh proofs, therefore proving big-omega was not hard as we first learned about proofs of big-oh. Professor's summary about under-estimation and over-estimation really help me to follow the step: for under-estimation, removing positive terms or multiplying negative terms while removing negative terms or multiplying positive terms for over-estimation. But we never changed the highest degree.
During the lecture, I felt uncomfortable about finding the values of C and B, but I have become confident to choosing the values of C and B after the tutorial I had on Thursday because TA explains detailed steps to find the values and proof structures too. Moreover his teaching of various ways to approaching method helped me to think and prove in right way which is an appropriate method to the problem.
For the general statements about big-Oh, similar to proofs of big-Oh and big-Omega, I still confused to choose the values of B and C because now I have big-Oh and big-Omega in just one statement. I do not know when I need to use max(B, B') and choose B' = B something like that.
I believe I feel more comfortable as I solve many problem sets, and read course notes. Also next Tutorial would help me to figure out how to choose the appropriate values of B and C.
Hello Kim,
ReplyDeleteYou are completely right about underestimating and overestimating.Just one thing. You said that we should multiply negative terms, but I think that multiplying by a negative term may change the inequality.
As for choosing B and C, a good idea would be to look at the lecture exercises and figure out why that B and C are chosen. I explain a little bit about choosing a B and include a different example dealing with Big-Oh proofs in my Blog. You could access it by using the following link: http://ttesttrying.blogspot.ca/2014/11/csc-165-big-oh-of-polynomials-non.html
All the best,
Christian