CMSC 351:Spring 2011 Michelle HugueCMSC351 Final Exam ReferenceAsymptotic Notations.Θ(g(n)) = {f(n): there exist positive constants c1, c2, and n0such that 0 ≤ c1g(n) ≤ f (n) ≤ c2g(n) for alln ≥ n0}.O(g(n)) = {f(n): there exist positive constants c and n0such that 0 ≤ f(n) ≤ cg(n) for all n ≥ n0}.Ω(g(n)) = {f(n): there exist positive constants c and n0such that 0 ≤ cg(n) ≤ f(n) for all n ≥ n0}.f(n) = o(g(n)) if limn→∞f(n)g (n)= 0.f(n) = ω(g(n)) if limn→∞f(n)g (n)= ∞.f(n) ∼ g(n) if f(n) = g(n) + o(g(n)).Logarithms.a = blogbalogc(ab) = logca + logcblogban= n logbalogba =logcalogcblogb(1/a) = −logbalogba =1logabalogbn= nlogbaaf(n)= ef(n) ln a(logaf(n))0=f0(n)f(n) ln a(af(n))0= ln af0(n)af(n)Quadratic Formula.ax2+ bx + c = 0 ⇒ x =−b ±√b2− 4ac2a1Summations.Simple Arithmetic Series:nXk=1k = 1 + 2 + ··· + n =n(n + 1)2nXk=1k2= 1 + 4 + ··· + n2=n(n + 1)(2n + 1)6nXk=1k3= 1 + 8 + ··· + n3=n2(n + 1)24General Arithmetic Series:nXk=mk = 1 + 2 + ··· + n =(n − m + 1)(n + m)2Geometric series:nXk=0xk= 1 + x + +x2··· + xn=xn+1− 1x − 1x 6= 1∞Xk=0xk=11 − x|x| < 1Integration rules - for an increasing function f(x):Zba−1f(s)ds ≤bXi=af(i) ≤Zb+1af(s)dsfor a decreasing function g(x):Zb+1ag(s)ds ≤bXi=ag(i) ≤Zba−1g(s)dsRecurrences.“AMT: Ambitious Master Theorem”:T (n) =aT (n/b) + cndn > 1f n = 1impliesT (n) =f +cab−d−1nlogba− (cndab−d−1) =Θ(nlogba) a > bdΘ(nd) a < bdnd(f + c logbn) = Θ(ndlogbn) a = bd.Miscelleneous.Stirling’s Approximation:n!
View Full Document
Unlocking...