Class Notes (838,811)
CS 137 (16)
Lecture 17

# Programming Lecture 17.docx

2 Pages
90 Views

School
Department
Computer Science
Course
CS 137
Professor
Andrew Morton
Semester
Fall

Description
Ninja Mutant Programming Lecture 17 November 15, 2012 Big O Notation  Let f(x) be a function over real numbers  O(f(x)) is a set of functions  g(x) ∈ O(f(x)) if and only if there exists M>0 and x 0uch that |g(x0| ≤ M|f(x)| for all x>x0  Eg: o 3x + 2 ∈ O(x ) 2  Proof:  If x>1, then |3x + 2| = 3x ≤ 5x = 5|x |2 o 5 is M o x is f(x)  |3x + 2| ≤ M|x | for all x>x0 o Constant: 6sinx ∈ O(1)  Proof:  If x>0, then |6sinx| ≤ 6 o 6=M o f(x)=1 o Polynomial: g(x) is any polynomial n n-1  g(x) = anx + a n-1 + … + a1  g(x) = O(x )  Proof: n n-1  If x>1, then | n x + an-1 + … + a 1 ≤ |an|x + |an-1 n-1+ … + |a1| ≤ (|an| + |n-1+ … + |a 1)x n  Holds if x0=1 and M= ∑  As a result, if n ≤ m then x ∈ O(x ) 4 76 o Eg: x ∈ O(x ) o Logarithmic: log x a O(log x) b  Proof:  If x>1 then |loga(x)| = loa (x) = lob (x) / lbg (a) = |lbg (x)| / bog (a)  M is |logb(x)|  f(x) is lob (a)
More Less

Related notes for CS 137
Me

OR

Join OneClass

Access over 10 million pages of study
documents for 1.3 million courses.

Join to view

OR

By registering, I agree to the Terms and Privacy Policies
Already have an account?
Just a few more details

So we can recommend you notes for your school.