COMP 250 Lecture Notes - Lecture 12: Aluva, Product Rule
14 Oct 2015
School
Department
Course
Professor
Document Summary
De nition: f(n) is o(g) i n0 n, c r : f(n) c g(n) n n0. Intuition: f(n) is o(g(n)) if f(n) grows at most as fast as some constant times g(n), for large n. Important: the running time of selection sort on an array of n elements was 1 + 5n + 13n2, which is o(n2). But it is also o(n3), and o(n4), and o(any function that grows at least as fast as n2). However, we usually try to give the snuggest big-oh description possible. O(g(n)) can be seen as the set of all functions f(n) that are o(g(n)): o(g(n)) = {f(n) : c, n0, n n0, f(n) c g(n)}. Then we can write n2 + 10n + 2 o(n2). We have the following (incomplete) hierarchy of big-oh classes: O(1) o(log n) o: o(n) o(nk) o(2n, o(1): functions bounded above by a constant. f(n) = 100 o(1), 10 + sin(n) o(1).
