# CS 173: Skills list for Examlet 12

• Big O
• Define what it means for a function f to be O(g) (big O of g) and Θ(g) (theta of g) where g is another function.
• For specific functions f and g, identify whether f is O(g), Θ(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), Θ(g) by identifying c and k as in the definitions.
• Algorithm Analysis
• Know that the running time of an algorithm is the number of steps taken by the algorithm. Typically, we assume that each line in the pseudo code is one step.
• Given a simple iterative algorithm, know how to compute an upper bound on its running time as a function of the length of the input.
• Know how to get Big O/Theta analysis of the running time of simple algorithms.
• Pigeon Hole Principle
• Be able to state and apply the Pigeonhole Principle to problems.
• Know generalize pigeon hole principle and apply it to problems.
• Apply the pigeonhole principle in writing proofs.
• Principle of Inclusion-Exclusion
• Know the Principle of Inclusion-Exclusion. You will be expected to remember the rule for two sets and three sets. If a problem requires using this for more than 3 sets, the principle will be given as part of the problem.
• Apply it to problems to compute the size of a set expressed as a union of other sets. Students will be expected to be able to reduce a counting question to one in which the principle of inclusion-exclusion can be applied, by defining appropriate sets.