CS161 Questions and Answers | New One | Grade A+

Asymptotic Notation Ans: the classification of runtime complexity that uses functions that indicate only the growth rate of a bounding function Big-Oh Notation Ans: Represents the upper bound of the run-time of an algorithm, aka worst-case complexity O(g(n)) = { f(n): there exist positive constants c and n0 such that 0 ≤ f(n) ≤ cg(n) for all n ≥ n0 } Little-Oh Notation (o) Ans: The not asymptotically tight upper bound of an algorithm (removes equality in Big-Oh) o(g(n)) = { f(n): for any positive constant c, there exists a positive contact n0 such that 0 ≤ f(n) cg(n) for all n ≥ n0 } Theta Notation (Θ) Ans: Encloses the function/run-time from above and below, and is used to for analyzing the average-case complexity of an algorithm Θ (g(n)) = {f(n): there exist positive constants c1, c2 and n0 such that Θ (g(n)) = {f(n): there exist positive constants c1, c2 and n0 such that 0 ≤ c1 * g(n) ≤ f(n) ≤ c2 * g(n) for all n ≥ n0} Note: Θ(g) is a set ≤ c1 * g(n) ≤ f(n) ≤ c2 * g(n) for all n ≥ n0} Note: Θ(g) is a set Omega-Notation (Ω) Ans: The lower bound of run-time of an algorithm, aka Best Case complexity Ω(g(n)) = { f(n): there exist positive constants c and n0 such that 0 ≤ cg(n) ≤ f(n) for all n ≥ n0 } Permutation Ans: The number of ways objects can be ordered that can be created from a particular set. Permutation Formula Ans: nPr = n!/(n-r)