This was probably the most hefty lecture of the semester. We took big-Oh proofs, which tend to be somewhat to moderately difficult themselves, and learned how to prove general properties (ie: if f is in big-Oh of g, then g is in big-Omega of f). Basically we were given a statement (ie: f is in O(g)) which provided us with a constant and breaking point, and we had to figure out how to mould those variables to prove the consequent (ie: g is then in Ω(f)).
An interesting example (which was asked on A3) was to prove that for any two functions f and g, f is in O(g) or Ω(g). I originally tried to prove this but then realized that cyclic functions or a simplified Dirichlet function would prove this statement false. Hopefully with a bit more practice these proofs will come easier to me!
No comments:
Post a Comment