Difference between revisions of "Comparing Algorithms - Big O"
(→Time complexities:) |
|||
| Line 2: | Line 2: | ||
=== Time complexities: === | === Time complexities: === | ||
| + | |||
===== Constant complexity - O(1)===== | ===== 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)===== | ===== 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)===== | ===== Logarithmic complexity - O(log n)===== | ||
| + | An algorithm with logarithmic complexity is better than a linear complexity for searching, because it will grow in time but not as fast. | ||
| + | |||
===== Linearithmic complexity - O(nlog n)===== | ===== Linearithmic complexity - O(nlog n)===== | ||
===== Polynomial complexity - O(n<sup>k</sup>)===== | ===== Polynomial complexity - O(n<sup>k</sup>)===== | ||
===== Exponential complexity - O(k<sup>n</sup>)===== | ===== Exponential complexity - O(k<sup>n</sup>)===== | ||
===== Factorial complexity - O(n!)===== | ===== Factorial complexity - O(n!)===== | ||
Revision as of 11:23, 15 May 2017
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.
Contents
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 but not as fast.
