Asymptotic Notations RAM The Random Access Machine RAM stands for Random Access Machine which is a very useful model of computation can access any memory location in constant time each basic instruction requires one unit of time running time proportional to the number of operations We will study functions that is asymptotically nonnegative i e there exists constant such that 0 for all Four important summations 1 2 3 4 n n n 1 2 1 1 2 1 4 1 8 1 2 n 1 1 2 n 1 1 1 2 1 x x2 x3 xn 1 xn 1 1 x provided that x 1 12 22 32 n2 n n 1 2n 1 6 1 1 2 1 3 1 4 1 n ln n 1 n ln n 1 Proofs Proofs Proofs Takeaways 1 2 3 4 n n n 1 2 1 x x2 x3 xn 1 xn 1 1 x provided x 1 12 22 32 n2 n n 1 2n 1 6 1 1 2 1 3 1 4 1 n ln n 1 n ln n 1 We will use these frequently in this course Know them and their variants by heart Definitions of Big O Big and Big Big O asymptotic upper bound Big asymptotic lower bound Commonly uses choices of g n 1 log n n n log n n2 n3 2n Proof example for Big O Example O 1 O 5 O 1000000 f n 1 for all n 1 f n 0 for all n 1 f n 1 1 n for all n 1 f n 1 1 n n for all n 1 f n 10000000000 for all n 1 What about f n n What about f n log n Is O 1 equal to O 5 Example O log n If f n O 1 then f n O log n f n 1 1 3 1 n for all n 1 What about f n n What about f n log n 2 Example O n O 2n 5 O 3n 1000000 If f n O 1 then f n O n f n n for all n 1 f n 8n 10000 for all n 1 What about f n n2 What about f n n log n Is O n equal to O 2n 5 Example O n2 f n 1 2 3 4 n for all n 1 What about f n n3 What about f n n2 log n Example O n3 f n 12 22 32 n2 for all n 1 What about f n n4 What about f n n3 log n Proof example for Big Example 1 5 0 0001 f n 1 for all n 1 f n log n for all n 1 f n n for all n 1 f n n2 for all n 1 f n 2n for all n 1 What about f n 0 What about f n 1 n Is 1 equal to 5 Example log n f n 1 1 3 1 n for all n 1 What about f n 10000 Example n 2n 5 3n 1000000 f n n for all n 1 f n 0 0001n 10000 for all n 1 What about f n log n Is n equal to 2n 5 Example 1 5 f n 1 for all n 1 f n 1 1 n n for all n 1 f n 0 01 for all n 1 f n 1000 for all n 1 If f n O 1 and f n 1 then f n 1 If f n 1 then f n O 1 and f n 1 Example n 5n If f n O n and f n n then f n n If f n n then f n O n and f n n Takeaways find a pair that works cf and Nf and prove using the definition The pair of constants are not unique You just need to To prove f n O g n you need to find the constants To prove f n g n you need to find the constants To prove f n g n you need to find the constants cf and Nf and prove using the definition cf df Nf and prove using the definition Asymptotic bounds Asymptotic bounds Example f n 1000n for all n g n n for all n f n g n implies f n O g n f n O g n does not imply f n g n We have f n O g n Similarly f n g n does not imply f n g n Mathematical Proofs for Asymptotic Notations There are two main methods to analyze asymptotic notations Method 1 Use definitions Method 2 Use limit on the ratio of the two functions If then f n g n If then f n O g n If then f n g n Some Facts O 1 O ln n O n O n ln n O n2 n2 n ln n n ln n 1 Commonly used bad notations When we read f n O g n read it as f n O g n When we read f n g n read it as f n g n When we read O n O n2 read it as O n O n2 When we read n2 n read it as n2 n Properties Properties Example Proof Summary The Random Access Machine Four commonly used formulas Big O Big Big notations
View Full Document
Unlocking...