Week 9 Slog

Week 9!

This weeks lecture is very mathematically orientated as we started looking at proofs of big-Oh using limit techniques. The first half of the lecture focused on proving Big Oh using its pure definition. Using proof structures and techniques we have learnt previously, I found it fairly easy to grasp the idea of a direct big Oh proof because I simply have to follow the quantifiers and pick a c and B that works. The harder part of a direct proof of big Oh comes when we have more complicated polynomials with various degrees. For instance, I found the prove for 7n^6 - 5n^4 + 2n^3 in O(6n^8 - 4n^5 + n^2) quite challenging as we had to deal with a lot of inequalities. Making a wise choice of c in these proofs are also very challenging. I finally understood the logic behind when I look at the actual proof as I saw how professor tries to overestimate the function f(x) and underestimate the function in O. Next, we looked at disproving big Oh by proving a statement's negation. This part was fairly straightforward and I was able to digest the proofs fully.

The second half of the lecture looked at non polynomial proofs, which was when the lecture gets very mathematical. Yet, I found it particularly enjoyable when I saw a relation between the definition of big Oh and the definition of limit when a function tends to infinity as I never noticed such correlation. We looked at the example 2^n in O(n^2) and the proof was completed after applying l'opital's rule and picking n as max (n', B) as both definition can be satisfied. Ultimately, I learnt a lot in this lecture and I enjoyed it very much.