Big O notation

For functions that are nonnegative for sufficiently large inputs, f(n) is O(g(n)) if there are positive constants c and n₀ such that f(n) ≤ c·g(n) for every n ≥ n₀. In words, after some threshold, g(n) multiplied by a fixed constant bounds f(n) from above. The constants cannot vary with n. For example, 3n² + 4n + 5 is O(n²), because its growth is eventually bounded by a constant multiple of n². It is also O(n³), but O(n²) is a tighter upper bound.

Computer scientists use Big O to describe how a resource measure changes as an algorithm’s input grows. The resource may be running time, memory, comparisons, or another operation count; a particular analysis should say which measure and computational model it uses. For example, a procedure that scans all n items in a list performs work proportional to n and is O(n), under a model that counts each inspection as constant work. A binary search on a sorted array repeatedly halves the remaining search range and takes O(log n) comparisons in the worst case.

Asymptotic analysis focuses on sufficiently large input sizes. When simplifying a polynomial expression such as 5n² + 3n + 8, the n² term eventually dominates the lower-order terms, and the constant multiplier is absorbed into the bound; the expression is therefore O(n²). Common growth classes include O(1), O(log n), O(n), O(n log n), O(n²), and exponential bounds such as O(2ⁿ). These classes help compare how resource use may scale, but actual performance also depends on implementation, hardware, input size, and constant factors.

Big O states an asymptotic upper bound; it does not intrinsically mean worst case. Best-case, average-case, and worst-case analyses describe which inputs of each size are being considered. Each of those measures can be expressed with Big O. A tight upper bound can also be described using Θ notation when matching upper and lower bounds are established; Ω notation expresses an asymptotic lower bound. These notations distinguish the type of mathematical bound from the choice of input case.

The capital O is read “big oh” and is commonly associated with the German word Ordnung, meaning order. The notation arose in mathematical analysis before becoming standard in computer science. It should not be confused with the Greek letter omicron, or treated as an equality: f(n) = O(g(n)) conventionally means that f belongs to the class of functions bounded asymptotically by g, not that the two functions are identical.