Anonymous user
O: Difference between revisions
m
added an ;Also see (for a Wiki reference).
(Added ordered list of notations) |
m (added an ;Also see (for a Wiki reference).) |
||
| (4 intermediate revisions by 3 users not shown) | |||
Line 1:
[[Category:Encyclopedia]]
[[Category:Encyclopedia]]'''Complexity'''. In computer science the notation O(P(n)) is used to denote asymptotic behavior of an algorithm, usually its complexity in terms of execution time or memory consumption. Here ''P'' is an algebraic function of ''n'', usually polynomial or logarithmic. ''n'' describes the size of the problem. The meaning of O(P(n)) is that the complexity grows with n as P(n) does.▼
;Complexity:
▲
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).
Here are some typical
:* O(e<sup>n</sup>) exponential
:* O(n<sup>k</sup>) for some fixed ''k'' ('polynomial')
:* O(n<sup>3</sup>) cubic
:* O(n<sup>2</sup>) quadratic
:* O(n*log(n)) fastest possible time for a [[:Category:Sorting Algorithms|comparison sort]]
:* O(n) linear
:* O(log(n)) logarithmic
:* O(1) constant
▲Here are typical Big-O's listed slowest to fastest (that is, slower algorithms have Big-O's near the top):
;Also see:
| |||