Tenth Lecture - November 11th 2014

Annnnnnnd, results for Term Test 2 are out. As expected, I didn't do well, but the class average was surprisingly low too. Anyway, there is always the final exam.

Just a recap of the method used to develop big-O proofs. Since the initial function will not grow faster than the second equation, you want to under-estimate the "variable" on the right side while over-estimating the "variable" on the left side of the big-O. Then finally, you put them together and pick a c value large enough to make the right side an upper bound.

Now, for proofs with big-Omega, you're doing literally the exact opposite, while picking a c value small enough to make the right side a lower bound.

As a summary, this is important to remember.

After this, we proceeded to prove general statements instead of functions. Um, don't know how to put this in words, but use c' and B' wisely. Here's how you do it.