Written by Supakorn Laohasongkram on September 3rd, 2014
It's one thing to write a working algorithm; but another to write one that works yet performs well. The performance for an algorithm is measured by how much resources an algorithm requires to perform a task. These can be the time, space, cpu, and memory it requires. However, there is another measurement which this article will look at specifically. It analyzes how algorithm performs in relation to the size of input. This measurement is called "Big-O".
Big O notation is the rate of performance for an algorithm to output as the size of the input increases. The techical term for this rate is known as "Complexity". The lower the complexity the better an algorithm performs as size of input increases.
Big-O mainly cares about Big Input
Big-O ignores all smaller constants and other slow growings terms and mainly differentiate an algorithm based on its general pattern.
For example, if...
T(n) = n + n**2.Imagine inputing some really big number like 1,000,000 into variable "n". The equation would then be...
T(10000000) = 10000000 + 10000000*10000000one millions times one millions is much more significant than the plus one million in front. So in this case, the constant like plus one million is ignored. And what you get is simply...
T(n) = N**2And we could say "T(n) grows at the order of (n ** 2) or the Big-O of this algorithm is (N ** 2)."
General Types of Big-O
Depending on the algorithm, we could generalize each algorithm's Big-O relation to its size of input as such...
| Size of Input | constant | logarithmic | linear | quadratic | cubic | |
|---|---|---|---|---|---|---|
| n | O(1) | O(log N) | O(N) | O(N log N) | O(N2) | O(N3) |
| 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| 2 | 1 | 1 | 2 | 2 | 4 | 8 |
| 4 | 1 | 2 | 4 | 8 | 16 | 64 |
| 8 | 1 | 3 | 8 | 24 | 64 | 512 |
| 16 | 1 | 4 | 16 | 64 | 256 | 4,096 |
| 1,024 | 1 | 10 | 1,024 | 10,240 | 1,048,576 | 1,073,741,824 |
| 1,048,576 | 1 | 20 | 1,048,576 | 20,971,520 | 1012 | 1016 |
Let's look at one example of Binary Search Algorithm. And determine what type of Big-O it is.
Binary Search
Binary search is a technique used to search sorted data sets. It works by selecting the middle element of the data set, essentially the median, and compares it against a target value. If the values match it will return success. If the target value is higher than the value of the probe element it will take the upper half of the data set and perform the same operation against it. Likewise, if the target value is lower than the value of the probe element it will perform the operation against the lower half. It will continue to halve the data set with each iteration until the value has been found or until it can no longer split the data set.
This type of algorithm is described as O(log N). The iterative halving of data sets described in the binary search example produces a growth curve that peaks at the beginning and slowly flattens out as the size of the data sets increase e.g. an input data set containing 10 items takes one second to complete, a data set containing 100 items takes two seconds, and a data set containing 1000 items will take three seconds. Doubling the size of the input data set has little effect on its growth as after a single iteration of the algorithm the data set will be halved and therefore on a par with an input data set half the size. This makes algorithms like binary search extremely efficient when dealing with large data sets.
Big-O measures a algorithm based on its worst case senario.
It is essential to understand that Big-O is always measured from the worst case senario of that particular algorithm. For example, if the algorithm has different paths of the if and elsif statements, to measure Big-O would requires the algorithm to take the longest and most demanding path as the measurement.
Conclusion
Big-O measures the performance of an algorithm in relation to the size of input. Since Complexity measures ONLY how well an algorithm function, complexity affects performance but not the other way around. Even though Big-O is a good indicator of how a program might perform but this is still very theoretical. According to my research, a better and more practical measurement would be to use benchmark. For further reading, please go the reference section to learn more.