# Definition:Algorithm

## Contents

## Definition

An **algorithm** is a finite set of **instructions** (or **rules**) that defines a sequence of **operations** for solving a particular **computational problem** for all **problem instances** for some **problem set**.

An **algorithm** must have the following properties:

### Finiteness

An **algorithm** must **terminate** after a finite number of **steps**.

### Definiteness

Each **step** of an algorithm must be **precisely defined**.

### Inputs

An **algorithm** has zero or more **inputs**.

These are values supplied either:

These **inputs** are taken from specified sets of objects.

### Outputs

An **algorithm** has one or more **outputs**.

These are values which are specifically determined by the inputs.

### Effectiveness

An **algorithm** is supposed to be **effective**.

That is, its **operations** must be basic enough to be able to be done **exactly** and in a finite length of time by, for example, somebody using pencil and paper.

## Parts of an Algorithm

### Step

An algorithm consists of a finite set of **steps**, uniquely identified by means of a label, conventionally numeric.

A **step** of an algorithm consists of:

- an
**operation**

- an
**instruction**as to what the algorithm is to do next, which will be one of the following:

- $(3): \quad$ To
**terminate**.

- $(3): \quad$ To

### Operation

In an algorithm, an **operation** is part of a step of that algorithm.

It consists of one of two things:

- an
**action**

or:

- a
**condition**.

### Action

In an algorithm, an **action** is part of a step of that algorithm.

It is an operation which changes the state of the algorithm in some manner.

### Condition

In an algorithm, a **condition** is part of a step of that algorithm.

It is an operation which determines the outcome of a decision as to which step to execute next,

### Comment

In an algorithm, a **comment** is a piece of explanatory information that helps the reader of that algorithm understand it better.

## Formal Specification

An **algorithm** can be implemented formally as a computational method $\left({Q, I, \Omega, f}\right)$ as follows:

Let $A$ be a finite set of symbols.

Let $A^*$ be the set of all collations on $A$:

- $\left\{ {x_1 x_2 \cdots x_n: n \ge 0, \forall j: 1 \le j \le n: x_j \in A}\right\}$

The states of the computation are encoded so as to be represented by elements of $A^*$.

Let $N \in \\Z_{\ge 0}$.

Let $Q$ be the set of all ordered pairs $\left({\sigma, j}\right)$ where $\sigma \in A^*, j \in \Z: 0 \le j \le N$.

Let $I \subseteq Q$ such that $j = 0$.

Let $\Omega \subseteq Q$ such that $j = N$.

Let $\theta, \sigma \in A^*$.

Then $\theta$ **occurs in $\sigma$** if and only if $\sigma$ has the form:

- $\alpha \theta \omega$

where $\alpha, \omega \in A^*$.

Let $f$ be a mapping of the following type:

- $f \left({\left({\sigma, j}\right)}\right) = \begin{cases}\left({\sigma, a_j}\right) : & \sigma_j \text { does not occur in } \sigma \\ \left({\alpha \theta_j \omega, b_j}\right) : & \alpha \text { is the shortest element of $A^*$ such that } \sigma = \alpha \theta_j \omega\end{cases}$
- $f \left({\left({\sigma, N}\right)}\right) = \left({\sigma, N}\right)$

## Analysis

There are two primary methods for analyzing **algorithms** formally:

### Correctness

The primary method of validity for **algorithms** is using a Proof of Correctness.

This is correctness through verification of the **algorithm** accomplishing its purpose formally, and terminating in $k$ finite steps.

### Complexity

An algorithm may be analysed in the context of its **complexity**.

This is typically via measures of run-times using big-O, or big-omega, or big-theta notation.

Complexity can be through 3 main types of analysis:

- Average-Case Analysis, using a distribution of cases to find an average case of the algorithm run-time for analysis
- Best-Case Analysis, using the best possible problem instance of the algorithm for analysis
- Worst-Case Analysis,using the worst possible problem instance of the algorithm for analysis

## Historical Note

The word **algorithm** is a recent addition to the English language. It was still absent from major dictionaries as late as $1957$.

## Linguistic Note

The word **algorithm** ultimately derives from the name Muhammad ibn Musa al-Khwarizmi.

It is strongly believed that it is the result of linguistic evolution of the archaic term **algorism**, with which **algorithm** should not (and probably will not) be confused.

The term was seen in German literature in its Latin form **algorithmus** at around the time of Gottfried Wilhelm von Leibniz, where the classical algorithms were referenced.

## Sources

- 1990: Thomas H. Cormen, Charles E. Leiserson and Ronald L. Rivest:
*Introduction to Algorithms*... (next) - 1997: Donald E. Knuth:
*The Art of Computer Programming: Volume 1: Fundamental Algorithms*(3rd ed.) ... (previous) ... (next): $\S 1.1$: Algorithms