Discussion 6: Intro to Asymptotics And Bits Christine Zhou Agenda Announcements And time to fill out surveys Asymptotics Review Problem 1,2 Bits and Bitwise Operators Problem 3 Announcements Midterm grades have been released! Place to Vent (ANONYMOUS): tinyurl.com/placetovent HW3 due yesterday TLDR: Make sure everything works on the instructional account Start Project 1 if you haven’t already! (PLEASE FILL OUT TODAY) Discussion survey: tinyurl.com/disc6cz Asymptotics: Big Ө(...) Called “big theta notation” R(N) = runtime, f(N) = function, k’s = constants The runtime can be both upper and lower bounded by the function Let’s say R(N) = 3n3 + 2n2 + 1 What is a good f(N), k1, k2? f(N) = n3, k1 = 2, k2 = 4 Asymptotics: Big O(...) Called “big oh notation” R(N) = runtime, f(N) = function, k = constant The function is an upper bound on the runtime DOES NOT MEAN WORST CASE True or false? N2 ∈ O(N2) N2 ∈ O(N500) N log N ∈ O(N) log N ∈ O(N2) Asymptotics: Big Ω(...) Called “big omega notation” R(N) = runtime, f(N) = function, k = constant The function is a lower bound on the runtime DOES NOT MEAN BEST CASE True or false? N2 ∈ Ω(N2) N ∈ Ω(1) N2 ∈ Ω(N3) 1 Basic Algorithmic Analysis Solutions: 1. f ∈ 𝛳(g) 2. f ∈ O(g) 3. f ∈ O(g) 4. f ∈ Ω(g) 5. f ∈ 𝛳(g) 2 Practice with Runtime 2 Practice with Runtime Bits Each number has a bit representation 01110 = 0*24 + 1*23 + 1*22 + 1*21 + 0*20 = 14 Bitwise Operators OR (|) 0 __ 0 0 0 0 __ 1 0 1 1 __ 1 1 1 x << y: shift the bit representation of x by y to the left (rest are filled with 0’s) AND (&) If x is 10011 and y is 2 x << y is 01100 x >> y: shift the bit representation of x by y to the right (rest are filled with 0’s) If x is 10011 and y is 2 3 A Bit with some Bits Let’s figure out what this question is asking first... Complete the following method such that it does what it is intended to do: given a list of integers, it returns an i