Eighth Lecture - October 28th, 2014

To begin, this is probably the most important thing I learned today. This structure is important to follow on tests and assignments, and it works even when you have no idea what you are doing. Also, assignment 2 is due next Monday but I'm confident in most of my proofs.

Now, moving onto a bit of review from the past few weeks.

1) How to prove a = b ?

➔ Prove (a ≤ b) ∧ (a ≥ b)

2) Assume two integers a < b

➔ a ≤ b - 1 # two integers differ by at least 1

3) When the statement seems kind-of trivial but

proving directly looks messy

➔ try contradiction

Today we learned about the definitions of big-O and Omega, as well as the worst case analyses of two algorithms (which I didn't quite understand).

In short, big-O expresses the relationship between two functions; where the first function is ultimately upper-bounded by the function shown after the big-O; this means that the initial function also grows no faster than the final function. Big-Omega is the exact opposite. The first function is lower-bounded by the second function expressed after big-Omega.