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).
- 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.)