CS 173, Fall 2014: Skills list for tenth examlet

• Big O
  • Define what it means for a function f to be asymptotically smaller than g (<< g), O(g) and/or θ(g). where g is another function.
  • For specific functions f and g, identify whether f is asymptotically smaller than g (<< g), O(g) and/or θ(g).
  • Know the asymptotic relationships among key primitive functions: constant, log n, n, n log n, polynomials of higher orders, exponentials, factorial.
  • Given functions f and g, prove that f is O(g) and/or θ(g).
• Induction
  • Use induction to prove claims involving inequalities
• Recursion Trees
  • Given a recursively defined function, find its closed form by drawing a recursion tree and adding up the work at all levels. (Examples would look like those presented in the textbook, e.g. the level sums are constant or increase in a pattern based on the key summations given above.)