# Computationally Expensive Algorithm

A Computationally Expensive Algorithm is an algorithm with high computational complexity (that requires a large number of steps to complete relative to its task input size).

**Context:**- It can (typically) be for an Intractable Computational Task.

**Counter-Example(s):**- an Inefficient Algorithm, whose task time performance is significantly higher than the theoretically optimal fo the task.
- a Computationally Inexpensive Algorithm.
- a Memory Intensive Algorithm.

**See:**Computational Complexity Theory, Exponential Algorithm, NP-hard.

## References

### 2009

- http://en.wikipedia.org/wiki/Computationally_expensive
- 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.