BigTheta

Big Theta notation, written as Θ, is used in computer science to describe a tight bound on the growth rate of a function as the input size n becomes large. It indicates that the function grows at the same rate as another function, up to constant factors.

Formally, a function f(n) is in Θ(g(n)) if there exist positive constants c1, c2 and n0 such that for all n ≥ n0, c1·g(n) ≤ f(n) ≤ c2·g(n). In this relation, g(n) is typically a positive function that describes the growth rate, and f(n) is the function being measured. The idea is to ignore constant factors and lower-order terms for large n.

Big Theta is a two-sided bound and is thus a tight bound. It implies both an upper bound (Big-O) and a lower bound (Big-Omega): if f(n) ∈ Θ(g(n)), then f(n) ∈ O(g(n)) and f(n) ∈ Ω(g(n)). Conversely, if f(n) ∈ O(g(n)) and f(n) ∈ Ω(g(n)), then f(n) ∈ Θ(g(n)).

Examples help illustrate the concept. If f(n) = 3n^2 + 2n + 1 and g(n) = n^2, then f(n) ∈ Θ(g(n)) because for large n, f(n) is bounded above and below by constant multiples of n^2. Similarly, f(n) = n log n is Θ(n log n) with g(n) = n log n.

Big Theta is primarily used to express the asymptotic running time or space complexity of algorithms, focusing on growth rate as n grows large and suppressing constant factors.