Lecture 3: Algorithm Analysis!Foundational Data Structures!(Review of Some 280 Material)!Asymptotic Algorithm Analysis!An algorithm with"complexity f(n) is"said to be not slower"than another algorithm"with complexity g(n)"if f(n) is bounded by"g(n) for large n!!Commonly written as"f(n) = O(g(n))"(read: f(n) is big-Oh g(n)),!a.k.a. the asymptotic (or big-Oh) notation!Big-Oh – Definition!f(n) = O(g(n)) if and only if there are constants!c > 0!n0 ≥ 0!}"such that f(n) ≤ c g(n) whenever n ≥ n0!00.511.522.50 1f (n) = n g(n) = n2!Is n = O(n2)?!n0 = 1!Let!f(n) = 8n + 128!g(n) = n2!Is f(n) = O(g(n))?!Is 8n + 128 ≤ c n2?!!Let c = 1, clearly, for n = 8, f(n) > g(n)!At what value of n0 is g(n) > f(n), ∀n ≥ n0?!How about for c = 2 and c = 4?!f (n) = 8n + 128!g(n) = n2!g(n) = 2n2!g(n) = 4n2!6.75 10.3 16 8 Big-Oh – Example!Big-Oh – Definition!As long as there is a c > 0, and n0 ≥ 0 such that"c•g(n) ≥ f(n) for all n ≥ n0, we say that f(n) = O(g(n))!In this example, 8n + 128 = O(n2)!!Mathematically:!f (n) = O(g(n)) iff ∃ c > 0, n0 ≥ 0 | ∀n, n ≥ n0, f (n) ≤ c g(n)!O(g(n)) = { f (n): ∃ c > 0, n0 ≥ 0 | ∀n, n ≥ n0, 0 ≤ f (n) ≤ c g(n)}"!So more accurately, f(n) ∈ O(g(n))!but conveniently people write f(n) = O(g(n)),!though NOT f(n) ≤ O(g(n))!Big-Oh – Definition!In other words, we only care about LARGE n, it doesn’t matter what c is!• obviously, c cannot be 10100 (one googol, the conjectured upper bound on the number of atoms in the observable universe)!!Also, asymptotically, n2 + k = O(n2), k constant (Why?)!Big-Oh: Sufficient"(but not necessary) Condition!If n→∞limf (n)g(n)⎛⎝⎜⎜⎜⎞⎠⎟⎟⎟⎟= c < ∞⎡⎣⎢⎢⎤⎦⎥⎥ then f (n) is O(g(n))limn→∞log n2n⎛⎝⎜⎜⎜⎞⎠⎟⎟⎟= limn→∞12n⎛⎝⎜⎜⎜⎞⎠⎟⎟⎟= 0 = c < ∞∞ / ∞Use L'Hôpital's Rule⇒ log2n = O(2n)log2n = O(2n)?f (n) = log2ng( n) = 2nCondition does not hold but nevertheless it is true that"f(n) = O(g(n))!sinn100⎛⎝⎜⎜⎜⎞⎠⎟⎟⎟= O(100)?f (n) = sinn100⎛⎝⎜⎜⎜⎞⎠⎟⎟⎟g(n) = 100limn→∞sinn100⎛⎝⎜⎜⎜⎞⎠⎟⎟⎟100⎛⎝⎜⎜⎜⎜⎜⎜⎜⎜⎜⎞⎠⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟L’Hôpital’s Rule!If limx→cf (x) = limx→cg(x) = 0 or ± ∞and limx→cf '(x) g'(x) exists thenlimx→cf (x)g(x)= limx→cf '(x)g'(x)wikipedia!Also useful, derivative of log:!ddxlogb(x) =1x ln(b)ddxln( f (x)) =f '(x)f (x)Log Identities!Identity! Example!loga(xy) = logax + logay! log2(12) ="loga(x/y) = logax – logay! log2(4/3) ="loga(xr) = r logax! log28 ="loga(1/x) = –logax! log21/4 =" log79 =!!k = log2n iff 2k = n ! logaa = ? !!loga1 = ?!Identity! Example!a(n+m) = anam! 25 = !a(n–m) = an/am! 23–2 = !(a(n))m = anm!(22)3 = !!!2-4 ="a–1= ?!!a0 = ?!!a1 = ?!Power Identities!logax =log xlog a=ln xln aa−n=1anBig-Oh: We Can Drop Constants!c > 0, n0≥ 0 such that f (n) ≤ c⋅ g(n), ∀n ≥ n03n2 + 7n + 42 = O(n2)?!f(n) = 3n2 + 7n + 42!g(n) = n2!c = 5!g(n) = 5n2!Definition!n0!Sufficient Condition!n→∞limf (n)g(n)= c < ∞=n→∞lim3n2+ 7n + 42n2⎛⎝⎜⎜⎜⎞⎠⎟⎟⎟⎟=n→∞lim6n + 72n⎛⎝⎜⎜⎜⎞⎠⎟⎟⎟=n→∞lim62⎛⎝⎜⎜⎜⎞⎠⎟⎟⎟Big-Oh – Common Mistakes!Mistake #0: f(n) = O(g(n)) ⇒ f(n) = g(n) (NOT)!Mistake #1: If f1(n) = h(n) and f2(n) = h(n) then"f1(n) = f2(n); it follows that if f1(n) = O(g(n)) and f2(n) = O(g(n)) means f1(n) = f2(n) (NOT)!Mistake #2: f(n) = O(g(n)) ⇒ g(n) = O–1(f(n)) (NOT)!(There’s no O–1()!)!Is f(n) = O(2n)?!Is f(n) = O(n2)?!Is f(n) = O(n log n)?!Is f(n) = O(n)?!Is f(n) = O(log n)?!!Let f(n) be the"complexity of your"code, how fast would you advertise it as?!While f(n) = O(g(n))  f(n) = g(n), you want to pick a g(n) that is as close to f(n) as possible (a “tight” bound) !How Fast is Your Code? !05101520250 1 2 3 4 5 6 7 8 9 10n log n!n!1!log n!n2!2n!n!runtime!f (n)About Big-Oh!Asymptotic analysis deals with the performance of algorithms for LARGE input sizes!!Big-Oh provides a short-hand to express upper bound, it is not an exact notation!• be careful how big c is!• be careful how big n0 must be!!Big-Oh asymptotic analysis is language independent!Big-Oh – Rules!Rule 1: For f1(n) = O(g1(n)) and f2(n) = O(g2(n))"⇒ f1(n) + f2(n) = O(max(g1(n), g2(n))!Example: f1(n) = n3 ∈ O(n3), f2(n) = n2 ∈ O(n2)"⇒ f1(n) + f2(n) = O(?)!Rule 2: For f1(n) = O(g1(n)) and f2(n) = O(g2(n))"⇒ f1(n) * f2(n) = O(g1(n)*g2(n))!• If your code calls a function within a loop, the complexity of your code is the complexity of the function you call times the loop’s complexity!Rule 3: If f(n) = O(g(n)) and g(n) = O(h(n))"then f(n) = O(h(n))!Big-Oh – More Common Mistakes!Mistake #3: Let f(n) = g1(n)*g2(n)"If f(n) ≤ cg1(n) where c = g2(n),"then f(n) = O(g1(n)) (NOT)!Mistake #4: Let f1(n) = O(g1(n)), f2(n) = O(g2(n)),"and g1(n) < g2(n) ⇒ f1(n) < f2(n) (NOT)!Counter-example:"f1(n) = ?"g1(n) = ?"f2(n) = ? "g2(n) = ?!Relatives of Big-Oh!Big-Omega (Ω()): asymptotic lower bound!For f (n) > 0, ∀n ≥ 0, f (n) = Ω(g(n)) if"∃ c > 0, n0 > 0 | ∀n, n ≥ n0, f (n) ≥ c g(n)!h1(n) = O(h2(n)) ⇔ h2(n) = Ω(h1(n))!!Big-Theta (Θ()):!f (n) = Θ(g(n)) iff"f (n) = O(g(n)) and"f (n) = Ω(g(n))!f (n) grows as fast as g(n)!Big-Theta!Does f (n) = Θ(g(n)) ⇒ g(n) = Θ(f (n))?!Does f (n) = Θ(g(n)) ⇒ f (n) = g(n)?!Does f (n) = Θ(g(n)) ⇒ f (n) is the same order as g(n)?!Relatives of Big-Oh!little-oh (o()):!f (n) = o(g(n)) if f (n) = O(g(n)) but f (n) ≠ Θ(g(n))!f (n) = o(g(n)) if ∃ n0 > 0 | ∀c > 0, ∀n, n ≥ n0, f (n) ≤ c g(n)!In contrast to O(), o() is forall c > 0, whereas O()"only requires there exists c > 0; so O() is sloppier"than o(), which is why we use it more often!!Example: 2n2 = O(n2) is asymptotically tight, but 2n = O(n2) is not!!little-omega (ω()):!f (n) = ω(g(n)) iff g(n) = o(f (n))!In the Limit! O() : f (n) = O(g(n)) ⇔ f (n) ≤ c1g(n) and limn→∞f (n)g(n)≤ c1Ω() : f (n) = Ω(g(n)) ⇔ f (n) ≥ c2g(n) and limn→∞g(n)f (n)≤ c2Θ() : f (n) = Θ(g(n)) ⇔ both limn→∞f (n)g(n)≤ c1 and limn→∞g(n)f (n)≤ c2o() : f (n) = o(g(n)) ⇔ limn→∞f (n)g(n)= 0ω() : f (n) = ω(g (n)) ⇔ limn→∞f (n)g(n)= ∞The Common Case:"Empirical Performance Evaluation!If n0 > the common case n, the asymptotic analysis result is not very useful . . . .!To determine the common case performance,"given known workload, run empirical performance measurement/evaluation!Note