Big Theta

/bɪɡ ˈθeɪ.tə/ · Noun · Development · Origin: 1976

Definitions

  1. Asymptotic notation (Θ) that provides a tight bound on a function's growth rate, meaning the function grows both no faster and no slower than the given rate. f(n) = Θ(g(n)) means f is bounded above and below by g, up to constant factors.

    In plain English: A way of saying an algorithm takes exactly this much time (up to a constant multiplier), not just 'at most' this much. It's the precise version of Big O.

    Example: "Merge sort is Θ(n log n) — not just O(n log n). It always takes n log n time, even in the best case."

Related Terms