CMSC 351 Spring 2011 Michelle Hugue CMSC351 Exam 2 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 k 1 2 n k 1 n X k 2 1 4 n2 k 1 n X n n 1 2 n n 1 2n 1 6 k 3 1 8 n3 k 1 n2 n 1 2 4 General Arithmetic Series n X k 1 2 n k m Geometric series n X n m 1 n m 2 xk 1 x x2 xn k 0 X xk k 0 1 1 x xn 1 1 x 1 x 6 1 x 1 Recurrences AMT Ambitious Master Theorem T n aT n b cnd f n 1 n 1 implies nlogb a a bd c cnd logb a f ab d 1 n ab 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...