Criss-cross algorithm: Difference between revisions

Revision as of 21:39, 23 June 2022

Revision as of 16:58, 16 July 2023

Line 26:

==Computational complexity: Worst and average cases==

[[File:Ellipsoid 2.png|thumb|right<!-- 400px -->|The worst-case computational complexity of Khachiyan's ''ellipsoidal algorithm'' is a polynomial. The ''criss-cross algorithm'' has exponential complexity.]]

The [[time complexity]] of an [[algorithm]] counts the number of [[arithmetic operation]]s sufficient for the algorithm to solve the problem. For example, [[Gaussian elimination]] requires on the [[Big oh|order&nbsp;of]]''&nbsp;D''³ operations, and so it is said to have polynomial time-complexity, because its complexity is bounded by a [[cubic polynomial]]. There are examples of algorithms that do not have polynomial-time complexity. For example, a generalization of Gaussian elimination called [[Buchberger's algorithm]] has for its complexity an <!--doubly --> exponential function of the problem data (the [[degree of a polynomial|degree of the polynomial]]s and the number of variables of the [[multivariate polynomial]]s). Because exponential functions eventually grow much faster than polynomial functions, an<!-- attained rather than upper bound --> exponential complexity implies that an algorithm has slow performance on large problems.