Computationally expensive

From Wikipedia, the free encyclopedia

A computationally expensive algorithm is one that, for a given input size, requires a relatively large number of steps to complete; in other words, one with high computational complexity. The "cost" of an algorithm relative to the size of its input is often represented using Big O notation.

For some expensive algorithms, there are less expensive counterparts. A traditional example in which multiple algorithms exist to achieve the same end is the class of sorting algorithms used to order a one-dimensional list. From the point of view of implementation, the so-called bubble sort is one of the simplest of these algorithms. It is, however, relatively computationally expensive, requiring more computation steps for a list of given size than almost any other standard algorithm. As such, bubble sort is virtually never used in practice. For real-life sorting problems, much more efficient algorithms are used, such as Quicksort; these, however, are somewhat more complicated in their implementation.

Often, the more general an algorithm, the more computationally expensive it is. For example, algorithms used for manipulating a generic matrix will work on a sparse matrix, but algorithms designed specifically for sparse matrices will be less expensive.