Is there a system behind the magic of algorithm analysis?

Question

There are lots of questions about how to analyze the running time of algorithms (see, e.g., runtime-analysis and algorithm-analysis). 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!}

Answer 1

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.

Further reading

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

• How to come up with the runtime of algorithms?
  How to describe algorithms, prove and analyse them?
• Why use comparisons instead of runtime for comparing two algorithms?
  How can we assume that basic operations on numbers take constant time?
  What constitutes one unit of time in runtime analysis?
• Solving or approximating recurrence relations for sequences of numbers
• Basics of Amortised Analysis

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

Answer 2

Execution Counts of Statements

There is another method, championed by Donald E. Knuth in his The Art of Computer Programming series. In contrast to translating the whole algorithm into one formula, it works independently from the code's semantics on the "putting things together" side and allows to go to a lower level only when necessary, starting from an "eagle's eye" view. Every statement can be analysed independently of the rest, leading to more clear calculations. However, the technique lends itself well to rather detailed code, not so much higher-level pseudo code.

The Method

It's quite simple in principle:

1. Assign every statement a name/number.
2. Assign every statement $S_i$ some cost $C_i$.
3. Determine for every statement $S_i$ its number of executions $e_i$.

4. Compute total costs

   $\qquad\displaystyle C = \sum_{i} e_i \cdot C_i$.

You can insert estimates and/or symbolic quantities at any point, weakening resp. generalising the result accordingly.

Be aware that step 3 can be arbitrarily complex. It's usually there that you have to work with (asymptotic) estimates such as "$e_{77} \in O(n \log n)$" in order to get results.

Example: Depth-first search

Consider the following graph-traversal algorithm:

dfs(G, s) do
  // assert G.nodes contains s
  visited = new Array[G.nodes.size]     1
  dfs_h(G, s, visited)                  2
end 

dfs_h(G, s, visited) do
  foo(s)                                3
  visited[s] = true                     4

  v = G.neighbours(s)                   5
  while ( v != nil ) do                 6
    if ( !visited[v] ) then             7
      dfs_h(G, v, visited)              8
    end
    v = v.next                          9
  end
end

We assume that the (undirected) graph is given by adjacency lists on nodes $\{0,\dots,n-1\}$. Let $m$ be the number of edges.

Just by looking at the algorithm, we see that some statements are executed equally often as others. We introduce some placeholders $A$, $B$ and $C$ for the execution counts $e_i$:

$\qquad\begin{array}{c|ccccccccc} i & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 \\ \hline e_i & A & A & B & B & B & B+C & C & B-1 & C \end{array}$

In particular, $e_8 = e_3-1$ since the every recursive call in line 8 causes a call of foo in line 3 (and one is caused by the original call from dfs). Furthermore, $e_6 = e_5 + e_7$ because the while condition has to be checked once per iteration but then once more in order to leave it.

It's clear that $A=1$. Now, during a correctness proof we would show that foo is executed exactly once per node; that is, $B = n$. But then, we iterate over every adjacency list exactly once and every edge implies two entries in total (one for each incident node); we get $C = 2m$ iterations in total. Using this, we derive the following table:

$\qquad\begin{array}{c|ccccccccc} i & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 \\ \hline e_i & 1 & 1 & n & n & n & 2m + n & 2m & n-1 & 2m \end{array}$

This leads us to total costs of exactly

$\qquad\begin{align*} C(n,m) = (C_1 + C_2 - C_8) &+\ n \cdot (C_3 + C_4 + C_5 + C_6 + C_8) \\ &+\ 2m \cdot (C_6 + C_7 + C_9) \;. \end{align*}$

By instantiating suitable values for the $C_i$ we can derive more concrete costs. For instance, if we want to count memory accesses (per word), we'd use

$\qquad\begin{array}{c|ccccccccc} i & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 \\ \hline C_i & n & 0 & 0 & 1 & 1 & 0 & 1 & 0 & 1 \end{array}$

and get

$\qquad\displaystyle C_{\text{mem}}(n,m) = 3n + 4m$.

Further reading

See at the bottom of my other answer.

Answer 3

Algorithm analysis, like theorem proving, is largely an art (e.g. there are simple programs (like Collatz problem) that we do not know how to analyze). We can convert an algorithm complexity problem to a mathematical one, as answered comprehensively by Raphael, but then in order to express a bound on the cost of an algorithm in terms of known functions, we're left to:

1. Use techniques we know from existing analyses, such as finding bounds based on recurrences we understand or sum/integrals we can compute.
2. Change the algorithm to something that we know how to analyze.
3. Come up with a completely new approach.