CMPT 125 Lecture 8: Lecture 8
18 Dec 2018
School
Department
Course
Professor
Document Summary
Formally: let f(n) and g(n) be two functions on positive integers. We say that f = o(g) if there exists a large enough constant c (e. g. c = 100) such that f(n) <= In other words, f = o(g) if there c>0 (e. g. c = 100) such that f(n)/g(n) <= c for all n. Discussion: f = o(g) captures the statement f is smaller than g . We could say f is smaller than g if f(n) < g(n) for all n. But then, we could could not write f(n) = o(n^2) in the example. We want to prove that f(n) < cn^3 for all n >= 1. Use the fact that n^4 <100 *2^n for all n>1. Let t(n) satisfy the recursive formula t(n) = t(n-1) + o(1) and t(1) = o(1). Proof: by definition, there exists c such that t(n) < t(n-1) + c.
