Analysis of algorithms

Definition

Let $\mathcal{A}$ be an algorithm with input set $I$, and let $\abs{x} \in \N$ be the size of an input $x \in I$. Let $c(x)$ be the number of elementary steps of $\mathcal{A}$ on $x$ in a fixed cost model. Let $I_n = \set{x \in I : \abs{x} = n}$ and assume each $I_n$ is finite and nonempty.

1. The worst-case running time of $\mathcal{A}$ is $T(n) = \max_{x \in I_n} c(x)$.
2. The best-case running time is $B(n) = \min_{x \in I_n} c(x)$.
3. Given a probability distribution $\Pr_n$ on each $I_n$, the average-case running time is $\bar{T}(n) = \sum_{x \in I_n} \Pr_n(x)\, c(x)$.

The analysis of algorithms is the determination of such functions, usually up to asymptotic order as $n \to \infty$. The same definitions with memory use in place of $c(x)$ give the space complexity.