Big Omega

/bɪɡ oʊˈmeɪ.ɡə/ · Noun · Development · Origin: 1976

Definitions

  1. Asymptotic notation (Ω) that provides a lower bound on a function's growth rate. f(n) = Ω(g(n)) means f grows at least as fast as g. Used to express that no algorithm for a problem can be faster than a certain rate.

    In plain English: The minimum amount of work an algorithm must do. It's the 'at least this slow' guarantee — a floor on performance.

    Example: "Comparison-based sorting is Ω(n log n) — you literally cannot do better without exploiting the structure of the data."

Related Terms