Big-Oh

Note: This post covers both Weeks 8 and 9.

Prof. Zhang introduced the formal definitions of big-Oh and big-Omega in Week 8. We learned how to do some simple proofs involving them which were daunting at first but exposed to be quite easy by overestimating (for big-Oh proofs) or underestimating (for big-Omega proofs) the function. I’m glad we’ve had so much practice with proofs, because these were fairly easy to do. The most important part for me was understanding the intuition behind the proofs, which was covered very well in lecture.

We started off week 9 with both a midterm and the A2 due date They were both probably the most challenging pieces of coursework that we’ve done so far. We had quite a few hints in the previous lecture though so they were both fair.

This week we went much more in depth into big-Oh proofs, going over examples of negation and limit-based proofs. We started with a regular proof, but discovered that we could not only overestimate the function, but also underestimate the bound which makes dealing with more complex proofs a bit simpler (but lets the profs ask us to do more complex proofs on tests…). We also learned negations (which were fairly intuitive) and yet again, a proof involving limits. If the ratio of the bound divided by the function approaches infinity as n approaches infinity, we can determine that the bound grows more rapidly than the function and therefore the function is in big-Oh of the bound. We used l’Hopitals rule to simplify the limits and then followed with a regular big-Oh proof. This was a fairly complex proof so much like my classmate Aqib writes here, I had to attend office hours to fully understand how to do it. I like these proofs now though because you don’t have to find appropriate constants or breakpoints, the fact that the variables exist to prove big-Oh are given by the limit.