CSE310 Lecture02 The Computing Model and Asymptotic Notations Guoliang Larry Xue Department of CSE Arizona State University http optimization asu edu xue Guoliang Xue asu edu Topics of this lecture The RAM constant access of memory constant time for basic operations Counting and Four Important Summations Big Oh Big Omega Theta Notations definitions examples properties 2 Guoliang Xue asu edu RAM Random Access Machine RAM stands for Random Access Machine which is a very useful model of computation basic instruction can be performed in one unit of time running time is equivalent to the number of operations required We will study function f n that is asymptotically positive i e f n 0 for n large enough 3 Guoliang Xue asu edu Counting Techniques and Proof by Induction 1 2 3 4 n 12 22 32 n2 1 1 2 1 4 1 8 1 2 n 1 1 2 1 3 1 4 1 n 4 Guoliang Xue asu edu Big Oh And Big Omega Notations O g n f n constants c and N s t f n c g n for n N We also write f n O g n when f n is a member of O g n g n f n constants c and N s t f n c g n for n N We also write f n g n when f n is a member of g n O notation is used to determine an upper bound on the order of growth of a function notation is used to determine a lower bound on the order of growth of a function 5 Guoliang Xue asu edu Examples If f n 2n 3 then f n O n If f n n4 100n then f n O n4 If f n 1 2 n then f n O n 2 If f n 100n for even n and f n n 2 for odd n then f n O n2 Also f n n n is not O n2 Demonstrate proof styles in class 6 Guoliang Xue asu edu Properties If f n O h n and g n O h n then f n g n O h n If f n O g n and g n O h n then f n O h n If f n O g n and c is a nonnegative constant then c f n O g n What can you say about If f n O g n then g n f n 7 Guoliang Xue asu edu Theta Notation g n f n positive constants c1 c2 and N s t c1 g n f n c2 g n for n N We also write f n g n when f n is a member of g n f n g n iff f n O g n and g n O f n f n g n iff f n g n and g n f n Proofs and examples 8 Guoliang Xue asu edu Properties and Useful Functions Properties on pp 51 52 Exercises on pp 52 53 The ceiling and floor functions Other functions on pp 54 59 9 Guoliang Xue asu edu Summary The Random Access Machine Big Oh Big Omega Theta notations Properties and Commonly Used Functions 10 Guoliang Xue asu edu Readings and Exercises The materials covered in this lecture can be found in Section 3 1 Section 3 2 You need to read both sections Exercises 3 1 1 to 3 1 6 Exercises 3 2 1 3 2 2 and 3 2 3 first part 3 2 8 Problems 3 1 to3 4 Lecture 03 will be on recurrence equations To preview read Sections 4 1 to 4 5 11 Guoliang Xue asu edu
View Full Document
Unlocking...