View source for Comparing Algorithms - Big O

Big O Notation is a measure of how long or how much memory is needed to execute and algorithm. This uses the worst case scenario, so that you get the maximum time and memory usage. It uses n as the number of items.

=== Time complexities: ===

===== Constant complexity - O(1)=====
An algorithm with constant complexity means that the time taken doesn't increase regardless of the items that you process. So you could have  10000 items and it would take 1 second, and 100 items and it would still take 1 second.

===== Linear complexity - O(n)=====
An algorithm with linear complexity takes more time as you give it more items to process. So the larger the n value is, the longer it takes.
For example planting seeds in a small field would take longer than planting the same amount of seeds but spread out in a larger field.

===== Logarithmic complexity - O(log n)=====
An algorithm with logarithmic complexity is better than a linear complexity for searching, because it will grow in time in comparison with items, but not as fast. For example when you search a list, and see that it's not in the middle, it will cut the list in half and then it searches in that half, so the time is reduced as the list gets split.

===== Linearithmic complexity - O(nlog n)=====
As the input n grows, the time taken to process the queue, but the time taken will always grow faster than the quantity of the input. Like a comb sort.

===== Polynomial complexity - O(n<sup>k</sup>)=====
The time taken to process the input increases faster than the size of the input n. An example would be shaking hands, between two people only one is needed, however as the amount of people in increases there will have to be many more handshakes between the people. 1/2(n<sup>2</sup> - n) would be the time complexity for handshakes.

===== Exponential complexity - O(k<sup>n</sup>)=====
===== Factorial complexity - O(n!)=====