Skip to interview prep
Apexed

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 Ω.

Give the formal definitions of Big-O, Big-Omega and Big-Theta, plus little-o. — Data structures & algorithms interview question — Apexed