70. Give the formal definitions of Big-O, Big-Omega and Big-Theta, plus little-o.
EasyAlgorithm analysis
Technical
Show model answer
f(n) = O(g(n)) if there exist constants c > 0 and n0 such that 0 <= f(n) <= c·g(n) for all n >= n0. f(n) = Ω(g(n)) if there exist c > 0 and n0 such that f(n) >= c·g(n) >= 0 for all n >= n0. f(n) = Θ(g(n)) if both hold, so f is sandwiched between two constant multiples of g.
Little-o is the strict version: f(n) = o(g(n)) if f(n)/g(n) tends to 0, so for every c > 0 the bound eventually holds. For example 2n = O(n) but 2n is not o(n), while n = o(n log n). Little-omega is the strict counterpart of Ω.