Algorithm

computation

Definition

Algorithm

An algorithm for a problem $\mathcal{P}$ is a well-defined description of computational steps that allows us to solve an arbitrary instance of $\mathcal{P}$.

An algorithm has to be applicable on all instances of a problem, terminate after a finite number of steps, and return a correct result for the given problem.

Complexity

Definition

Algorithm Complexity

We base our considerations on the asymptotic worst-case complexity of an algorithm, i.e., by means of a function $f(\cdot )$, such that for every problem instance of size $n$, the answer can b computed in $O(f(n))$ operations (runtime), or respectively by means of $O(f(n))$ bits in memory (memory requirement).

Link to original

Variants

Greedy

Definition

Greedy Algorithm

An algorithm is called greedy if it constructs a solution incrementally using a local criterion, without foresight, to select the next solution component to be added.

Link to original