Complexity of algorithms

In computer science, Big O Notation is a notation for expressing the worst-case execution time for an algorithm.

It is generally written as $O(f(x_{1},x_{2},\ldots ,x_{n})),where<math>f$ is a function of zero or more parameters $x_{i}$ of the system. It roughly states that in the aymptotic case (i.e. as one or more of the system parameters extend towards their extremes), the actual execution time of the algorithm is bounded by $K\times f(x_{1},x_{2},\ldots ,x_{n})\$forsomepositiveconstantK.BigONotationisattractivetocomputerscientistsbecauseitexpressesthecomplexityofanalgorithmwithoutrestrictingthestatementtoaparticular[[computerarchitecture]]ortimeperiod;evenifcomputersgetfaster,orifthealgorithmisswitchedfromaPCtoaApple,theworstcaseexecutiontimeofanalgorithmdoesnotchange.Additionally,whencomparingtwoalgorithms,itisreadilyapparentwhichwillexecutefasterintheextremecase.Mostcommonly,onewillsee*Polynomialtimealgorithms,**<math>O(1)$ --- Constant time --- the time necessary to perform the algorithm does not change in response to the size of the problem.

• • $O(n)$ --- Linear time --- the time grows linearly with the size (n) of the problem.
  • $O(n^{2})$ --- Quadratic time --- the time grows quadratically with the size (n) of the problem. Please note that, by convention, one only writes the highest-degree term for polynomial time.
• Sub-polynomial time algorithms (grow slower than polynomial time algorithms).
• $O(logn)$ -- Logarithmic time
• Super-polynomial time algorithsm (grow faster than polynomial time algorithms).
• $O(n!)$
• $O(2^{n})$

Despite the examples, Big O Notation can express execution time as a function of multiple examples.

See Also

• complexity theory
• complexity class