The Big O notation, where O stands for ‘order of’, is concerned with what happens for very large values of n. For example, if a sorting algorithm performs n2 operations to sort just n elements, then that algorithm would be described as an O(n2 ) algorithm
When expressing complexity using the Big O notation, constant multipliers are ignored. So, an O(4n) algorithm is equivalent to O(n), which is how it should be written.
If f(n) and g(n) are the functions defined on a positive integer number n, then
f(n) = O(g(n))
That is, f of n is Big–O of g of n if and only if positive constants c and n exist, such that f(n)£cg(n). It means that for large amounts of data, f(n) will grow no more than a constant factor than g(n). Hence, g provides an upper bound. Note that here c is a constant which depends on the following factors:
- the programming language used,
- the quality of the compiler or interpreter
- the CPU speed
- the size of the main memory and the access time to it
- the knowledge of the programmer, and
- the algorithm itself, which may require simple but also time-consuming machine instructions
If f(n) ≤ cg(n), c > 0, ∀ n ≥ n0 , then f(n) = O(g(n)) and g(n) is an asymptotically tight upper bound for f(n)
Categories of Algorithms
According to the Big O notation, we have five different categories of algorithms:
- Constant time algorithm: running time complexity given as O(1)
- Linear time algorithm: running time complexity given as O(n)
- Logarithmic time algorithm: running time complexity given as O(log n)
- Polynomial time algorithm: running time complexity given as O(nk ) where k > 1
- Exponential time algorithm: running time complexity given as O(2n )
Limitations of Big O Notation
There are certain limitations with the Big O notation of expressing the complexity of algorithms. These limitations are as follows:
- Many algorithms are simply too hard to analyse mathematically.
- There may not be sufficient information to calculate the behaviour of the algorithm in the average case.
- Big O analysis only tells us how the algorithm grows with the size of the problem, not how efficient it is, as it does not consider the programming effort.
- It ignores important constants. For example, if one algorithm takes O(n2 ) time to execute and the other takes O(100000n2 ) time to execute, then as per Big O, both algorithm have equal time complexity. In real-time systems, this may be a serious consideration