CSC 345 Lecture Notes - Lecture 3: Big O Notation, Asymptotic Analysis, Bubble Sort

• School: University of Arizona
• Department: Computer Science Main
• Course: CSC 345
• Professor: Lu

Document Summary

10/20/14 8:34 am: we will use this for tight upper bounds let f(n) and g(n) be functions that map positive integers to positive real numbers. O( g(n) ) if there exists a contstant c > 0 and integer constant n0 0 such that f(n) c * g(n) for every integer n n0. O(n*log(n)) , note : the log is base 2, but base really doesnt matter, see below logan = logb n logb a. If f(n) = a mn m + am 1nn 1 + + a2n2 + a1n + a0 then f(n) is o(n m ) Proof: f (n) = m i = 0 aini m i = 0. | ai | ni = n m * | ai | ni m n m m i = 0 m i = 0. , since ni m is always smaller than 1 for n 1 m if we set c = And g(n) = n m then we get.