CMPT 225 Lecture 2: Lecture 2

• School: Simon Fraser University
• Department: Computing Science
• Course: CMPT 225
• Professor: David Mitchell

Document Summary

Then: let n* be the biggest values with max (n) F(n) > c*1 for all n within n. So: f(n) = o(1) iff f(n) = o(1037) or iff f(n) = o(10-6) because we can simply chose a c large enough. O(1000) = o(1/1000) = o(1) because will be bounded by some constant. This is because we are not looking at the input to determine how long it takes to run. So: f(n) = o(n) is equivalent to f(n) = o(17n) and o(n/17) because can chose c big enough. This allows us to wave away the constants. O(n) characterizes functions that don t grow faster than a straight line. Note: a functions that has time complexity o(1) also has time complexity o(n), O(n2) because by definition it is just an upper bound. Might get tricked by this on a question but is not an acceptable answer because it gives no useful info. For the functions f: n n and g:n n.