GroßOhNotation

GroßOhNotation, in German often written Groß-Oh-Notation, is the term used for the Big-O notation in computer science. It provides a way to express an upper bound on the growth rate of a function as the input size n increases. Formally, 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)|. This expresses that f grows no faster than a constant multiple of g for large n.

Common examples: f(n) = 3n^2 + 2n + 1 is O(n^2); n log n is O(n^2). The base of logarithms is irrelevant because changing base multiplies by a constant.

It is used to analyze time and space complexity of algorithms. In practice, Big-O describes asymptotic upper bounds, not exact run times. It often ignores constant factors and lower-order terms, focusing on the dominant growth rate.

Related notations include Big-Theta (Θ), for a tight bound, and little-o (o) and little-omega (ω) for strict less-than or greater-than growth. Applications require identifying the right bound for the problem domain and input sizes.

Limitations: Big-O describes asymptotics, which may be a poor predictor for small inputs or systems with non-ideal performance. It also does not capture constant factors that can be relevant in practice.

Groß-Oh-Notation remains a standard tool in algorithm design, analysis, and teaching, with German texts typically using the term Groß-Oh-Notation.