A theoretical measure of the execution of an algorithm, usually the time or memory needed, given the problem size n, which is usually the number of items. Informally, saying some equation f(n) = ω (g(n)) means g(n) becomes insignificant relative to f(n) as n goes to infinity. Formal Definition: f(n) = ω (g(n)) means that for any positive constant c, there exists a constant k, such that 0 ≤ cg(n) < f(n) for all n ≥ k. The value of k must not depend on n, but may depend on c.