complexity

algorithm The level in difficulty in solving mathematically

posed problems as measured by the time, number of steps or

arithmetic operations, or memory space required (called time

complexity, computational complexity, and space complexity,

respectively).

The interesting aspect is usually how complexity scales with

the size of the input (the "scalability"), where the size of

the input is described by some number N. Thus an algorithm

may have computational complexity O(N^2) (of the order of the

square of the size of the input), in which case if the input

doubles in size, the computation will take four times as many

steps. The ideal is a constant time algorithm (O(1)) or

failing that, O(N).

See also NP-complete.

(1994-10-20)