Big O notation
Introduction
In the field of computer science, Big O notation is a mathematical notation that describes the limiting behavior of a function when the argument tends towards a particular value or infinity. It is a member of a family of notations invented by Paul Bachmann, Edmund Landau, and others, collectively called Bachmann–Landau notation or asymptotic notation.
Definition
In Big O notation, the statement "f(n) = O(g(n))" (or equivalently, "f(n) is O(g(n))") denotes that the function f(n) grows at a rate that is asymptotically less than or equal to the function g(n) for large values of n. In other words, there exists a constant M such that f(n) ≤ Mg(n) for all n greater than some value n0.
Usage in Computer Science
In computer science, Big O notation is used to classify algorithms according to how their running time or space requirements grow as the input size grows. It provides an upper bound on the time complexity of an algorithm, which makes it a useful tool for comparing the efficiency of different algorithms.
Time Complexity
The time complexity of an algorithm quantifies the amount of time taken by an algorithm to run, as a function of the size of the input to the program. The time complexity is usually expressed in terms of Big O notation. For example, if the time required by an algorithm on all inputs of size n is at most 5n^3 + 3n, the algorithm is said to be O(n^3).
Space Complexity
Similar to time complexity, the space complexity of an algorithm quantifies the amount of space or memory taken by an algorithm to run, as a function of the size of the input to the program. The space complexity is also usually expressed in terms of Big O notation.
Common Orders of Growth
In computer science, some common orders of growth in Big O notation include:
- Constant time: O(1)
- Logarithmic time: O(log n)
- Linear time: O(n)
- Linearithmic time: O(n log n)
- Quadratic time: O(n^2)
- Cubic time: O(n^3)
- Exponential time: O(2^n)
- Factorial time: O(n!)
Properties and Operations
Big O notation has several properties and operations that are used in the analysis of algorithms. These include:
- Transitivity: If f(n) = O(g(n)) and g(n) = O(h(n)), then f(n) = O(h(n)).
- Addition: If f(n) = O(h(n)) and g(n) = O(p(n)), then f(n) + g(n) = O(h(n) + p(n)).
- Multiplication: If f(n) = O(h(n)) and g(n) = O(p(n)), then f(n) * g(n) = O(h(n) * p(n)).
Criticism and Limitations
While Big O notation is a powerful tool for comparing the efficiency of algorithms, it does have its limitations. For example, it does not provide a precise measure of an algorithm's performance, but only an asymptotic upper bound. Furthermore, it does not take into account the specifics of a particular hardware or software environment, which can significantly affect an algorithm's performance.