CS 173: Skills list for Examlet 10

Big O

• Define what it means for a function f to be asymptotically smaller than g (f ≪ 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 (f ≪ 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).
• Given a set of asymptotic relationships, decide whether another similar relationship must hold.

Inequality proofs

• Direct proofs involving harder use of inequalities