CMSC 351 Spring 2011 Michelle Hugue CMSC351 Final Exam Reference Asymptotic Notations g n f n there exist positive constants c1 c2 and n0 such that 0 c1 g n f n c2 g 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 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 blogb a logc ab logc a logc b n n logb a logc a logc b logb a 1 loga b logb a logb a logb 1 a logb a alogb n nlogb a af n loga f n 0 ef n ln a f 0 n f n ln a af n 0 ln af 0 n af n Quadratic Formula 2 ax bx c 0 x 1 b b2 4ac 2a Summations Simple Arithmetic Series n X n n 1 2 k 1 2 n k 1 n X k 2 1 4 n2 k 1 n X n n 1 2n 1 6 n2 n 1 2 4 k 3 1 8 n3 k 1 General Arithmetic Series n X k 1 2 n k m Geometric series n X n m 1 n m 2 xn 1 1 x 1 xk 1 x x2 xn k 0 X 1 1 x xk k 0 x 6 1 x 1 Integration rules for an increasing function f x b Z f s ds b X a 1 b 1 Z f i f s ds a i a for a decreasing function g x b 1 Z g s ds a b X Z b g i g s ds a 1 i a Recurrences AMT Ambitious Master Theorem T n aT n b cnd f n 1 n 1 implies d nlogb a a bd f ab dc 1 nlogb a abcn d 1 T n nd a bd d d n f c logb n n logb n Miscelleneous Stirling s Approximation n 2 n 2 n n e a bd
View Full Document
Unlocking...