Discussion 7: Asymptotics II, Search Trees Christine Zhou Announcements Homework 2 due today, March 6! Homework 3 will be released on Thursday morning ○ Due Monday, March 11 Midterm 1 Regrade Requests due by this Friday at 11:59pm! SIgn up to meet with me if you’re interested! Resources: tinyurl.com/cs61b-christine-zhou Survey: tinyurl.com/cz-disc7-sp19 Notation: Big O, Big Omega, Big Theta Goal: Look at program complexity for large input Notations: ○ Big O - upper bound ○ Big Omega - lower bound ○ Big Theta - upper and lower bound O (Big O) Let f(n) and g(n) be positive real numbers on inputs of size n f ∈ O(g) if there is a constant c > 0 s.t. f(n) <= c g(n) Upper bounded by g(n) when n gets significantly large. Bound does not have to be tight. True or false? ○ ○ ○ ○ N2 ∈ O(N2) N2 ∈ O(N500) N log N ∈ O(N) log N ∈ O(N2) Ω (Big Omega) Let f(n) and g(n) be positive real numbers on inputs of size n f ∈ Ω(g) if there is a constant c > 0 s.t. f(n) >= c g(n) Lower bounded by g(n) when n gets significantly large. Bound does not have to be tight. True or false? ○ N2 ∈ Ω(N2) ○ N ∈ Ω(1) ○ N2 ∈ Ω(N3) Θ (Big Theta) Let f(n) and g(n) be positive real numbers on inputs of size n f ∈ Θ(g) if there is a constant c1 > 0 and c2 > 0 s.t. ○ C1 g(n) <= f(n) <= c2 g(n) for all c1 <= c2 Tightly bounded by g(n) when n gets significantly large. • f ∈ Ω(g) and f ∈ O(g) Introduction to Algorithms, Cormen, Leiserson, Rivest, Stein Conventions: No Constants Drop multiplicative constants and lower order terms ○ If our runtime is actually 2N^2 + N, we say the runtime is Theta(N^2) Any exponential dominates any polynomial Any polynomial dominates any logarithm Common Asymptotic Sets O(1): constant O(log n): logarithmic O(sqrt(n)): square root O(n): linear O(n log n): linearithmic O(n^2): quadratic O(n^3): cubic O(2^n): exponential O(n!): factorial Techniques for Analyzing Runtime Annotate your code ○ Write