Is there a system behind the magic of algorithm analysis?

There are lots of questions about how to analyze the running time of algorithms (see, e.g., and ). Many are similar, for instance those asking for a cost analysis of nested loops or divide & conquer algorithms, but most answers seem to be tailor-made.

On the other hand, the answers to another general question explain the larger picture (in particular regarding asymptotic analysis) with some examples, but not how to get your hands dirty.

Is there a structured, general method for analysing the cost of algorithms? The cost might be the running time (time complexity), or some other measure of cost, such as the number of comparisons executed, the space complexity, or something else.

This is supposed to become a reference question that can be used to point beginners to; hence its broader-than-usual scope. Please take care to give general, didactically presented answers that are illustrated by at least one example but nonetheless cover many situations. Thanks!

• Thanks go to the author(s) of StackEdit for making it convenient to write such long posts, and my beta readers FrankW, Juho, Gilles and Sebastian for helping me iron out a number of flaws earlier drafts had. – Raphael Apr 9 '14 at 13:04
• Hey @Raphael, this is wonderful stuff. I thought I would suggest putting it together as a PDF to circulate around? This sort of thing could become a really useful reference. – hadsed Apr 12 '14 at 4:23
• @hadsed: Thanks, I'm glad it's useful to you! For now, I prefer that a link to this post be circulated around. However, SE user content is "licensed under cc by-sa 3.0 with attribution required" (see page footer) so anyone can create a PDF from it, as long as attribution is given. – Raphael Apr 12 '14 at 7:31
• I am not especially competent on this, but is it normal that there is no reference to the Master theorem in any anwer? – babou Oct 12 '14 at 14:33
• @babou I don't known what "normal" means here. From my point of view, the Master theorem has no business being here: this is about analysing algorithms, the Master theorem is a very specific tool for solving (some) recurrences (and very roughly at that). Since the mathematics have been covered elsewhere (e.g. here) I have elected to cover only the part from algorithm to mathematics here. I give references to posts that deal with working the mathematics in my answer. – Raphael Oct 14 '14 at 9:06

Translating Code to Mathematics

Given a (more or less) formal operational semantics you can translate an algorithm's (pseudo-)code quite literally into a mathematical expression that gives you the result, provided you can manipulate the expression into a useful form. This works well for additive cost measures such as number of comparisons, swaps, statements, memory accesses, cycles some abstract machine needs, and so on.

Example: Comparisons in Bubblesort

Consider this algorithm that sorts a given array A:

 bubblesort(A) do                   1
n = A.length;                     2
for ( i = 0 to n-2 ) do           3
for ( j = 0 to n-i-2 ) do       4
if ( A[j] > A[j+1] ) then     5
tmp    = A[j];              6
A[j]   = A[j+1];            7
A[j+1] = tmp;               8
end                           9
end                             10
end                               11
end                                 12


Let's say we want to perform the usual sorting algorithm analysis, that is count the number of element comparisons (line 5). We note immediately that this quantity does not depend on the content of array A, only on its length $n$. So we can translate the (nested) for-loops quite literally into (nested) sums; the loop variable becomes the summation variable and the range carries over. We get:

$\qquad\displaystyle C_{\text{cmp}}(n) = \sum_{i=0}^{n-2} \sum_{j=0}^{n-i-2} 1 = \dots = \frac{n(n-1)}{2} = \binom{n}{2}$,

where $1$ is the cost for each execution of line 5 (which we count).

Example: Swaps in Bubblesort

I'll denote by $P_{i,j}$ the subprogram that consists of lines i to j and by $C_{i,j}$ the costs for executing this subprogram (once).

Now let's say we want to count swaps, that is how often $P_{6,8}$ is executed. This is a "basic block", that is a subprogram that is always executed atomically and has some constant cost (here, $1$). Contracting such blocks is one useful simplification that we often apply without thinking or talking about it.

With a similar translation as above we come to the following formula:

$\qquad\displaystyle C_{\text{swaps}}(A) = \sum_{i=0}^{n-2} \sum_{j=0}^{n-i-2} C_{5,9}(A^{(i,j)})$.

$A^{(i,j)}$ denotes the array's state before the $(i,j)$-th iteration of $P_{5,9}$.

Note that I use $A$ instead of $n$ as parameter; we'll soon see why. I don't add $i$ and $j$ as parameters of $C_{5,9}$ since the costs do not depend on them here (in the uniform cost model, that is); in general, they just might.

Clearly, the costs of $P_{5,9}$ depend on the content of $A$ (the values A[j] and A[j+1], specifically) so we have to account for that. Now we face a challenge: how do we "unwrap" $C_{5,9}$? Well, we can make the dependency on the content of $A$ explicit:

$\qquad\displaystyle C_{5,9}(A^{(i,j)}) = C_5(A^{(i,j)}) + \begin{cases} 1 &, \mathtt{A^{(i,j)}[j] > A^{(i,j)}[j+1]} \\ 0 &, \text{else} \end{cases}$.

For any given input array, these costs are well-defined, but we want a more general statement; we need to make stronger assumptions. Let us investigate three typical cases.

1. The worst case

Just from looking at the sum and noting that $C_{5,9}(A^{(i,j)}) \in \{0,1\}$, we can find a trivial upper bound for cost:

$\qquad\displaystyle C_{\text{swaps}}(A) \leq \sum_{i=0}^{n-2} \sum_{j=0}^{n-i-2} 1 = \frac{n(n-1)}{2} = \binom{n}{2}$.

But can this happen, i.e. is there an $A$ for this upper bound is attained? As it turns out, yes: if we input an inversely sorted array of pairwise distinct elements, every iteration must perform a swap¹. Therefore, we have derived the exact worst-case number of swaps of Bubblesort.

2. The best case

Conversely, there is a trivial lower bound:

$\qquad\displaystyle C_{\text{swaps}}(A) \geq \sum_{i=0}^{n-2} \sum_{j=0}^{n-i-2} 0 = 0$.

This can also happen: on an array that is already sorted, Bubblesort does not execute a single swap.

3. The average case

Worst and best case open quite a gap. But what is the typical number of swaps? In order to answer this question, we need to define what "typical" means. In theory, we have no reason to prefer one input over another and so we usually assume a uniform distribution over all possible inputs, that is every input is equally likely. We restrict ourselves to arrays with pairwise distinct elements and thus assume the random permutation model.

Then, we can rewrite our costs like this²:

$\qquad\displaystyle \mathbb{E}[C_{\text{swaps}}] = \frac{1}{n!} \sum_{A} \sum_{i=0}^{n-2} \sum_{j=0}^{n-i-2} C_{5,9}(A^{(i,j)})$

Now we have to go beyond simple manipulation of sums. By looking at the algorithm, we note that every swap removes exactly one inversion in $A$ (we only ever swap neighbours³). That is, the number of swaps performed on $A$ is exactly the number of inversions $\operatorname{inv}(A)$ of $A$. Thus, we can replace the inner two sums and get

$\qquad\displaystyle \mathbb{E}[C_{\text{swaps}}] = \frac{1}{n!} \sum_{A} \operatorname{inv}(A)$.

Lucky for us, the average number of inversions has been determined to be

$\qquad\displaystyle \mathbb{E}[C_{\text{swaps}}] = \frac{1}{2} \cdot \binom{n}{2}$

which is our final result. Note that this is exactly half the worst-case cost.

1. Note that the algorithm was carefully formulated so that "the last" iteration with i = n-1 of the outer loop that never does anything is not executed.
2. "$\mathbb{E}$" is mathematical notation for "expected value", which here is just the average.
3. We learn along the way that no algorithm that only swaps neighbouring elements can be asymptotically faster than Bubblesort (even on average) -- the number of inversions is a lower bound for all such algorithms. This applies to e.g. Insertion Sort and Selection Sort.

The General Method

We have seen in the example that we have to translate control structure into mathematics; I will present a typical ensemble of translation rules. We have also seen that the cost of any given subprogram may depend on the current state, that is (roughly) the current values of variables. Since the algorithm (usually) modifies the state, the general method is slightly cumbersome to notate. If you start feeling confused, I suggest you go back to the example or make up your own.

We denote with $\psi$ the current state (imagine it as a set of variable assignments). When we execute a program P starting in state $\psi$, we end up in state $\psi / \mathtt{P}$ (provided P terminates).

• Individual statements

Given just a single statement S;, you assign it costs $C_S(\psi)$. This will typically be a constant function.

• Expressions

If you have an expression E of the form E1 ∘ E2 (say, an arithmetic expression where ∘ may be addition or multiplication, you add up costs recursively:

$\qquad\displaystyle C_E(\psi) = c_{\circ} + C_{E_1}(\psi) + C_{E_2}(\psi)$.

Note that

• the operation cost $c_{\circ}$ may not be constant but depend on the values of $E_1$ and $E_2$ and
• evaluation of expressions may change the state in many languages,

so you may have to be flexible with this rule.

• Sequence

Given a program P as sequence of programs Q;R, you add the costs to

$\qquad\displaystyle C_P(\psi) = C_Q(\psi) + C_R(\psi / \mathtt{Q})$.

• Conditionals

Given a program P of the form if A then Q else R end, the costs depend on the state:

$\qquad\displaystyle C_P(\psi) = C_A(\psi) + \begin{cases} C_Q(\psi/\mathtt{A}) &, \mathtt{A} \text{ evaluates to true under } \psi \\ C_R(\psi/\mathtt{A}) &, \text{else} \end{cases}$

In general, evaluating A may very well change the state, hence the update for the costs of the individual branches.

• For-Loops

Given a program P of the form for x = [x1, ..., xk] do Q end, assign costs

$\qquad\displaystyle C_P(\psi) = c_{\text{init_for}} + \sum_{i=1}^k c_{\text{step_for}} + C_Q(\psi_i \circ \{\mathtt{x := xi\}})$

where $\psi_i$ is the state before processing Q for value xi, i.e. after the iteration with x being set tox1, ..., xi-1.

Note the extra constants for loop maintenance; the loop variable has to be created ($c_{\text{init_for}}$) and assigned its values ($c_{\text{step_for}}$). This is relevant since

• computing the next xi may be costly and
• a for-loop with empty body (e.g. after simplifying in a best-case setting with a specific cost) does not have zero cost if it performs iterations.
• While-Loops

Given a program P of the form while A do Q end, assign costs

$\qquad\displaystyle C_P(\psi) \\\qquad\ = C_A(\psi) + \begin{cases} 0 &, \mathtt{A} \text{ evaluates to false under } \psi \\ C_Q(\psi/\mathtt{A}) + C_P(\psi/\mathtt{A;Q}) &, \text{ else} \end{cases}$

By inspecting the algorithm, this recurrence can often be represented nicely as a sum similar to the one for for-loops.

Example: Consider this short algorithm:

while x > 0 do    1
i += 1          2
x = x/2         3
end               4


By applying the rule, we get

$\qquad\displaystyle C_{1,4}(\{i := i_0; x := x_0\}) \\\qquad\ = c_< + \begin{cases} 0 &, x_0 \leq 0 \\ c_{+=} + c_/ + C_{1,4}(\{i := i_0 + 1; x := \lfloor x_0/2 \rfloor\}) &, \text{ else} \end{cases}$

with some constant costs $c_{\dots}$ for the individual statements. We assume implicitly that these do not depend on state (the values of i and x); this may or may not be true in "reality": think of overflows!

Now we have to solve this recurrence for $C_{1,4}$. We note that neither the number of iterations not the cost of the loop body depend on the value of i, so we can drop it. We are left with this recurrence:

$\qquad\displaystyle C_{1,4}(x) = \begin{cases} c_> &, x \leq 0 \\ c_> + c_{+=} + c_/ + C_{1,4}(\lfloor x/2 \rfloor) &, \text{ else} \end{cases}$

This solves with elementary means to

$\qquad\displaystyle C_{1,4}(\psi) = \lceil \log_2 \psi(x) \rceil \cdot (c_> + c_{+=} + c_/) + c_>$,

reintroducing the full state symbolically; if $\psi = \{ \dots, x := 5, \dots\}$, then $\psi(x) = 5$.

• Procedure Calls

Given a program P of the form M(x) for some parameter(s) x where M is a procedure with (named) parameter p, assign costs

$\qquad\displaystyle C_P(\psi) = c_{\text{call}} + C_M(\psi_{\text{glob}} \circ \{p := x\})$.

Note again the extra constant $c_{\text{call}}$ (which might in fact depend on $\psi$!). Procedure calls are expensive due to how they are implemented on real machines, and sometimes even dominate runtime (e.g. evaluating the Fibonacci number recurrence naively).

I gloss over some semantic issues you might have with the state here. You will want to distinguish global state and such local to procedure calls. Let's just assume we pass only global state here and M gets a new local state, initialized by setting the value ofp to x. Furthermore, x may be an expression which we (usually) assume to be evaluated before passing it.

Example: Consider the procedure

fac(n) do
if ( n <= 1 ) do         1
return 1               2
else                     3
return n * fac(n-1)    4
end                      5
end


As per the rule(s), we get:

\qquad\displaystyle\begin{align*} C_{\text{fac}}(\{n := n_0\}) &= C_{1,5}(\{n := n_0\}) \\ &= c_{\leq} + \begin{cases} C_2(\{n := n_0 \}) &, n_0 \leq 1 \\ C_4(\{n := n_0 \}) &, \text{ else} \end{cases} \\ &= c_{\leq} + \begin{cases} c_{\text{return}} &, n_0 \leq 1 \\ c_{\text{return}} + c_* + c_{\text{call}} + C_{\text{fac}}(\{n := n_0 - 1\}) &, \text{ else} \end{cases} \end{align*}

Note that we disregard global state, as fac clearly does not access any. This particular recurrence is easy to solve to

$\qquad\displaystyle C_{\text{fac}}(\psi) = \psi(n) \cdot (c_{\leq} + c_{\text{return}}) + (\psi(n) - 1) \cdot (c_* + c_{\text{call}})$

We have covered the language features you will encounter in typical pseudo code. Beware hidden costs when analysing high-level pseudo code; if in doubt, unfold. The notation may seem cumbersome and is certainly a matter of taste; the concepts listed can not be ignored, though. However, with some experience you will be able to see right away which parts of the state are relevant for which cost measure, for instance "problem size" or "number of vertices". The rest can be dropped -- this simplifies things significantly!

If you think now that this is far too complicated, be advised: it is! Deriving exact costs of algorithms in any model that is so close to real machines as to enable runtime predictions (even relative ones) is a tough endeavour. And that's not even considering caching and other nasty effects on real machines.

Therefore, algorithm analysis is often simplified to the point of being mathematically tractable. For instance, if you don't need exact costs, you can over- or underestimate at any point (for upper resp. lower bounds): reduce the set of constants, get rid of conditionals, simplify sums, and so on.

A note on asymptotic cost

What you will usually find in literature and on the webs is the "Big-Oh analysis". The proper term is asymptotic analysis which means that instead of deriving exact costs as we did in the examples, you only give costs up to a constant factor and in the limit (roughly speaking, "for big $n$").

This is (often) fair since abstract statements have some (generally unknown) costs in reality, depending on machine, operating system and other factors, and short runtimes may be dominated by the operating system setting up the process in the first place and whatnot. So you get some perturbation, anyway.

Here is how asymptotic analysis relates to this approach.

1. Identify dominant operations (that induce costs), that is operations that occur most often (up to constant factors). In the Bubblesort example, one possible choice is the comparison in line 5.

Alternatively, bound all constants for elementary operations by their maximum (from above) resp. their minimum (from below) and perform the usual analysis.

2. Perform the analysis using execution counts of this operation as cost.
3. When simplifying, allow estimations. Take care to only allow estimations from above if your goal is an upper bound ($O$) resp. from below if you want lower bounds ($\Omega$).

Make sure you understand the meaning of Landau symbols. Remember that such bounds exist for all three cases; using $O$ does not imply a worst-case analysis.

There are many more challenges and tricks in algorithm analysis. Here is some recommended reading.

There are many questions tagged around that use techniques similar to this.

• maybe some reference and examples to the master theorem (and its extensions) for asymptotic analysis – Nikos M. Nov 13 '14 at 8:30
• @NikosM It is out of scope here (see also the comments on the question above). Note that I link to our reference post about solving recurrences which does present Master theorem et al. – Raphael Nov 13 '14 at 10:14