Properties of Algorithms

There are a few properties of algorithms which need to be understood before diving into understanding complexity. For the moment, we will only be looking at complexity of single variable algorithms (that is, single input). The multi-variable analysis is trivial to generalise.

Let $\Phi(i)$ be an algorithm with input $i$ and $\left\vert i\right\vert = n$, where $\left\vert\ldotp \right\vert: I \to \mathbb{Z}$, a measure of the length of input. Let $I$ and $S$ be the input and output sets respectively. Then an algorithm consists of two attributes:

1. Input $i$ with $i \in I$.
2. Output $s = \Phi(i)$ with $s \in S$

We can exploit these properties to try and understand algorithms better. In fact, these properties are the very things we use when we try to talk about the algorithmic complexity. Rather than describing the time it takes the algorithm to run on a computer - which would be machine dependant - we can in fact make measurements in terms of the length of input, say. This is clearly machine independent - which is what we actually want to achieve.