CSE310 Lecture02: The Computing Model and Asymptotic NotationsTopics of this lectureRAM: Random Access MachineCounting Techniques and Proof by InductionBig Oh And Big Omega NotationsExamplesPropertiesTheta NotationProperties and Useful FunctionsSummaryReadings and [email protected] Lecture02:CSE310 Lecture02:The Computing Model and Asymptotic NotationsThe Computing Model and Asymptotic NotationsGuoliang (Larry) XueDepartment of CSEArizona State Universityhttp://optimization.asu.edu/[email protected] of this lectureTopics of this lectureThe RAMconstant access of memoryconstant time for basic operationsCounting and Four Important SummationsBig Oh, Big Omega, Theta Notationsdefinitionsexamples[email protected]: Random Access MachineRAM: Random Access MachineRAM 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 [email protected] Techniques and Proof by InductionCounting Techniques and Proof by Induction1+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/[email protected] Oh And Big Omega NotationsBig Oh And Big Omega NotationsO(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 [email protected]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(n2).If f(n) = 100n for even n and f(n) = n2 for odd n, then f(n) = O(n2). Also f(n) = (n).n is not O(n2).Demonstrate proof styles in [email protected]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))[email protected] NotationTheta 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 [email protected] and Useful FunctionsProperties and Useful FunctionsProperties on pp. 51-52.Exercises on pp. 52-53.The ceiling and floor functions.Other functions on pp. 54—[email protected]The Random Access Machine.Big-Oh, Big-Omega, Theta notations.Properties and Commonly Used [email protected] and ExercisesReadings and ExercisesThe 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
View Full Document
Unlocking...