O: Difference between revisions

Content added Content deleted

Inline

Revision as of 08:43, 15 July 2020

Complexity. In computer science the notation O(f(n)) is used to denote an upper limit of the asymptotic behavior of an algorithm, usually its complexity in terms of execution time or memory consumption (space). Here f is a function of n, often a power or logarithm. n describes the size of the problem. The meaning of O(f(n)) is that the complexity grows with n at most as f(n) does.

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 complexity classes listed from 'slowest' to 'fastest' (that is, slower algorithms have Big-O's near the top):

O(eⁿ) exponential
O(n^k) for some fixed k ('polynomial')
O(n³) cubic
O(n²) quadratic
O(n*log(n)) fastest possible time for a comparison sort
O(n) linear
O(log(n)) logarithmic
O(1) constant

@@ Line 1: / Line 1: @@
+[[Category:Encyclopedia]]
-[[Category:Encyclopedia]]'''Complexity'''. In computer science the notation O(f(n)) is used to denote an upper limit of the asymptotic behavior of an algorithm, usually its complexity in terms of execution time or memory consumption (space). Here ''f'' is a function of ''n'', often a power or logarithm. ''n'' describes the size of the problem. The meaning of O(f(n)) is that the complexity grows with n at most as f(n) does.
+'''Complexity'''.
+In computer science the notation O(f(n)) is used to denote an upper limit of the asymptotic behavior of an algorithm, usually its complexity in terms of execution time or memory consumption (space). Here ''f'' is a function of ''n'', often a power or logarithm. ''n'' describes the size of the problem. The meaning of O(f(n)) is that the complexity grows with n at most as f(n) does.
 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 complexity classes listed from 'slowest' to 'fastest' (that is, slower algorithms have Big-O's near the top):
-*O(e<sup>n</sup>) ('exponential')
+:* &nbsp; O(e<sup>n</sup>) &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; exponential
-*O(n<sup>k</sup>) for some fixed ''k'' ('polynomial')
+:* &nbsp; O(n<sup>k</sup>) &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; for some fixed ''k'' ('polynomial')
-*O(n<sup>3</sup>) ('cubic')
+:* &nbsp; O(n<sup>3</sup>) &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; cubic
-*O(n<sup>2</sup>) ('quadratic')
+:* &nbsp; O(n<sup>2</sup>) &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; quadratic
-*O(n*log(n)) (fastest possible time for a [[:Category:Sorting Algorithms|comparison sort]])
+:* &nbsp; O(n*log(n))      &nbsp; &nbsp; &nbsp;                             fastest possible time for a [[:Category:Sorting Algorithms|comparison sort]]
+:* &nbsp; O(n)      &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; linear
-*O(n) ('linear')
-*O(log(n)) ('logarithmic')
+:* &nbsp; O(log(n)) &nbsp; &nbsp; &nbsp; &nbsp;                             logarithmic
+:* &nbsp; O(1)      &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; constant
-*O(1) ('constant')
 See also [[wp:Big_O_notation|Big O notation]]