O: Difference between revisions
Content added Content deleted
(Big-O is upper limit; names for typical complexity classes; some other minor modifications) |
m (Linkified a bit) |
||
| Line 3: | Line 3: | ||
The notation can also be used to describe a computational problem. In that case it characterizes the problem's complexity through the best known algorithm that solves it. |
The notation can also be used to describe a computational problem. In that case it characterizes the problem's complexity through the best known algorithm that solves it. |
||
Examples: searching in an unordered container of ''n'' elements has the complexity of O(''n''). Binary search in an ordered container with random element access is O(log ''n''). The term random access actually means that the complexity of access is constant, i.e. O(1). |
Examples: searching in an unordered container of ''n'' elements has the complexity of O(''n''). [[Binary search]] in an ordered container with random element access is O(log ''n''). The term random access actually means that the complexity of access is constant, i.e. O(1). |
||
Here are some typical complexity classes listed from 'slowest' to 'fastest' (that is, slower algorithms have Big-O's near the top): |
Here are some typical complexity classes listed from 'slowest' to 'fastest' (that is, slower algorithms have Big-O's near the top): |
||
| Line 10: | Line 10: | ||
*O(n<sup>3</sup>) ('cubic') |
*O(n<sup>3</sup>) ('cubic') |
||
*O(n<sup>2</sup>) ('quadratic') |
*O(n<sup>2</sup>) ('quadratic') |
||
*O(n*log(n)) (fastest possible time for a comparison sort) |
*O(n*log(n)) (fastest possible time for a [[:Category:Sorting Algorithms|comparison sort]]) |
||
*O(n) ('linear') |
*O(n) ('linear') |
||
*O(log(n)) ('logarithmic') |
*O(log(n)) ('logarithmic') |
||
*O(1) ('constant') |
*O(1) ('constant') |
||
See also [ |
See also [[wp:Big_O_notation|Big O notation]] |
||