Computationally expensive

﻿
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.

Additionally, the cost of a given action can apply to what kind of I/O is involved; fetching data from memory is usually considered inexpensive, whereas having to fetch memory from disk -- a far slower medium -- is considered expensive.

Wikimedia Foundation. 2010.

Look at other dictionaries:

• Television standards conversion — is the process of changing one type of TV system to another. The most common is from NTSC to PAL or the other way around. This is done so TV programs in one nation may be viewed in a nation with a different standard. The TV video is fed through a …   Wikipedia

• Crypt (Unix) — In Unix computing, crypt is the name of both a commonly available utility program and a C programming function. Though both are used for encrypting data, they are otherwise essentially unrelated. To distinguish between the two, writers often… …   Wikipedia

• Molecular dynamics — (MD) is a computer simulation of physical movements of atoms and molecules. The atoms and molecules are allowed to interact for a period of time, giving a view of the motion of the atoms. In the most common version, the trajectories of molecules… …   Wikipedia

• HSL and HSV — Fig. 1. HSL (a–d) and HSV (e–h). Above (a, e): cut away 3D models of each. Below: two dimensional plots showing two of a model’s three parameters at once, holding the other constant: cylindrical shells (b, f) of constant saturation, in this case… …   Wikipedia

• Nucleic acid design — can be used to create nucleic acid complexes with complicated secondary structures such as this four arm junction. These four strands associate into this structure because it maximizes the number of correct base pairs, with A s matched to T s and …   Wikipedia

• Bounding volume — A three dimensional model with its bounding box drawn in dashed lines. For building code compliance, see Bounding. In computer graphics and computational geometry, a bounding volume for a set of objects is a closed volume that completely contains …   Wikipedia

• crypt (Unix) — In Unix computing, crypt is the name of both a utility program and a C programming function. Though both are used for encrypting data, they are otherwise essentially unrelated. To distinguish between the two, writers often refer to the utility… …   Wikipedia

• Sequence alignment — In bioinformatics, a sequence alignment is a way of arranging the sequences of DNA, RNA, or protein to identify regions of similarity that may be a consequence of functional, structural, or evolutionary relationships between the sequences.… …   Wikipedia

• Folding@home — Original author(s) Vijay Pande Developer(s) Stanford University / Pande lab Initial release 2000 10 01 …   Wikipedia

• Computational phylogenetics — is the application of computational algorithms, methods and programs to phylogenetic analyses. The goal is to assemble a phylogenetic tree representing a hypothesis about the evolutionary ancestry of a set of genes, species, or other taxa. For… …   Wikipedia