onotation

Onotation, commonly referred to as asymptotic notation in computer science, is a collection of mathematical tools used to describe the limiting behavior of functions that arise in algorithm analysis. It provides a way to compare how running time or space usage grows as the input size n becomes large. The main components are Big-O, Big-Theta, Big-Omega, along with the related small-o and small-omega ideas.

Big-O notation describes an upper bound. A function f(n) is O(g(n)) if there exist constants c > 0 and n0 such that for all n ≥ n0, f(n) ≤ c g(n). It expresses that f does not grow faster than g up to a constant factor. Big-Theta denotes a tight bound: f(n) = Θ(g(n)) if there exist constants c1, c2 > 0 and n0 such that c1 g(n) ≤ f(n) ≤ c2 g(n) for all n ≥ n0. Here f and g grow at the same rate up to multiplicative constants. Big-Omega provides a lower bound: f(n) = Ω(g(n)) if there exist c > 0 and n0 such that f(n) ≥ c g(n) for all n ≥ n0.

Little-o and little-omega describe strict dominance. f(n) = o(g(n)) means that for every c > 0 there exists n0 with f(n) < c g(n) for all n ≥ n0. Conversely, f(n) = ω(g(n)) means that for every c > 0 there exists n0 with f(n) > c g(n) for all n ≥ n0.

Examples: f(n) = n^2 + n is Θ(n^2); f(n) = n log n is o(n^2). Onotation omits constants and lower-order terms to compare asymptotic efficiency, under a suitable computational model, and often focuses on worst-case behavior.