Big O notation
Big O notation
Big O notation is a mathematical notation used in computer science and mathematics to describe the limiting behavior of a function when the argument tends towards a particular value or infinity. In computer science, it is commonly used to classify algorithms according to how their running time or space requirements grow as the input size increases. It provides an asymptotic upper bound on the growth rate, allowing comparison of algorithm efficiency independently of hardware or implementation details.
Common orders
- Constant time – O(1): the operation takes the same amount of time regardless of input size.
- Logarithmic time – O(log n): the time grows logarithmically (e.g., binary search).
- Linear time – O(n): the time grows linearly with input size.
- Linearithmic time – O(n log n): typical for efficient sorting algorithms like Mergesort and Heapsort.
- Quadratic time – O(n^2): often arises from nested loops (e.g., bubble sort).
- Higher polynomial and exponential orders are also defined for more complex algorithms.
History
The notation was first introduced by the German mathematician Paul Bachmann in 1894 in his book Analytische Zahlentheorie. It was later popularized in computer science by Donald Knuth in the 1960s and 1970s, particularly in his series 2 , where he formalized its use for analyzing algorithms.