jsschools

Big-Theta Notation (Θ)

An asymptotic tight bound stating that a function grows at exactly the same rate as the bounding function — neither faster nor slower — up to constant factors.

Spec ↗

Syntax

f(n) = Θ(g(n))
// iff f(n) = O(g(n))  AND  f(n) = Ω(g(n))
// i.e., ∃ c₁, c₂ > 0, n₀ > 0 such that
// c₁·g(n) ≤ f(n) ≤ c₂·g(n) for all n ≥ n₀

Parameters

NameTypeRequiredDescription
f(n) function Yes The actual runtime or space function of the algorithm.
g(n) function Yes The tight bounding function.

Returns

boolean — True if f and g have the same asymptotic growth rate.

Examples

// Merge sort is Θ(n log n) in all cases —
// it always divides and merges regardless of input.
function mergeSort(arr) {
  if (arr.length <= 1) return arr;
  const mid = arr.length >> 1;
  const left  = mergeSort(arr.slice(0, mid));
  const right = mergeSort(arr.slice(mid));
  return merge(left, right);
}
function merge(a, b) {
  const out = []; let i = 0, j = 0;
  while (i < a.length && j < b.length)
    out.push(a[i] <= b[j] ? a[i++] : b[j++]);
  return [...out, ...a.slice(i), ...b.slice(j)];
}
console.log(mergeSort([5, 3, 8, 1, 9, 2]));
Output 
[ 1, 2, 3, 5, 8, 9 ]

// Linear scan is Θ(n) — always visits every element.
function sumAll(arr) {
  let s = 0;
  for (const x of arr) s += x; // exactly n iterations
  return s;
}
console.log(sumAll([1, 2, 3, 4, 5]));

// Quick sort is O(n²) but NOT Θ(n log n) — its worst case
// (already-sorted input with naive pivot) is Θ(n²).
console.log('Quick sort: O(n log n) avg, Θ(n²) worst — not tight');
Output 
15
Quick sort: O(n log n) avg, Θ(n²) worst — not tight

Notes

Θ is the most precise of the three notations — it pins down the exact asymptotic class. An algorithm with Θ(n log n) cannot be beaten by more than a constant factor using the same model of computation. Relationship summary: - Θ(f) ⊆ O(f) — every tight bound is an upper bound - Θ(f) ⊆ Ω(f) — every tight bound is a lower bound - Θ(f) = O(f) ∩ Ω(f) Algorithms with the same Θ class may differ hugely in practice due to constant factors and cache effects. Always profile on real data.

See also