Anonymous user
O: Difference between revisions
Big-O is upper limit; names for typical complexity classes; some other minor modifications
(Added ordered list of notations) |
(Big-O is upper limit; names for typical complexity classes; some other minor modifications) |
||
Line 1:
[[Category:Encyclopedia]]'''Complexity'''. In computer science the notation O(
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.
Line 5:
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
*O(
*O(n<sup>k</sup>) for some fixed ''k'' ('polynomial')
*O(
*O(n<sup>
*O(n*log(n)) (fastest possible time for a comparison sort)
*O(n) ('linear')
*O(log(n)) ('logarithmic')
*O(1) ('constant')
See also [http://en.wikipedia.org/wiki/Big_O_notation Big O notation]
|