COMP 250 Lecture 11: Lecture 11 - Big O Definition Examples

• School: McGill University
• Department: Computer Science (Sci)
• Course: COMP 250
• Professor: Mathieu Blanchette

Document Summary

Let f(n) and g(n) be two functions from the integers to the non-negative real numbers: f : n r+, g : n r+. We say that f(n) is o(g(n)) if and only if there exist constants c r and n n such that for all n n, f(n) c g(n). In more mathematical terms: f(n) is o(g(n)) i : c r, n n such that f(n) c g(n)) n n,. To prove that that a function f(n) is o(g(n)), one needs to nd c and n such that f(n) c g(n) n n. Let f(n) = 4n + 2 and g(n) = n. prove that f(n) is o(g(n)). We want to nd c and n such that 4n + 2 c n n n. choosing c 4 is not going to work. Then, we want to nd n such that 4n+2 5n n n. choosing n = 0 or n = 1 would not work.