Asymptotic Notations and Complexity Analysis: Fall 2002 CMSC 351 Document - Prof. Brian Th, Study notes of Algorithms and Programming

Download Asymptotic Notations and Complexity Analysis: Fall 2002 CMSC 351 Document - Prof. Brian Th and more Study notes Algorithms and Programming in PDF only on Docsity! CMSC 351:Fall 2002 Khuller & Postow Information CMSC251 Asymptotic Notations. Θ(g(n)) = {f(n): there exist positive constants c1, c2, and n0 such that 0 ≤ c1g(n) ≤ f(n) ≤ c2g(n) for all n ≥ n0}. O(g(n)) = {f(n): there exist positive constants c and n0 such that 0 ≤ f(n) ≤ cg(n) for all n ≥ n0}. Ω(g(n)) = {f(n): there exist positive constants c and n0 such that 0 ≤ cg(n) ≤ f(n) for all n ≥ n0}. Logarithms. a = blogb a logc(ab) = logc a + logc b logb a n = n logb a logb a = logc a logc b logb(1/a) = − logb a logb a = 1 loga b alogb n = nlogb a Stirling’s Formula. n! ≈ (n e )n√ 2πn Recurrences “Master Theorem”: T (n) = { aT (n/b) + cnd n > 1 f n = 1 implies T (n) =  ( f + c ab−d−1 ) nlogb a − cn d ab−d−1 = { Θ(nlogb a) a > bd Θ(nd) a < bd nd(f + c logb n) = Θ(nd logb n) a = bd . Facts: Number of leaves in a binary tree of height h is at most 2h. 1