# 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. 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? 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 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
• @Nikos M: my $0.02: while the master theorem works for several recurrences, it won't for many others; there are standard methods for solving recurrences. And there are algorithms for which we won't even have a recurrence giving the running time; some advanced counting techniques may be necessary. For someone with good math background, I suggest Sedgewick and Flajolet's exellent book, "Analysis of Algorithms", which has chapters such as "recurrence relations", "generating functions", and "asymptotic approximations". Data structures show up as occasional examples, and the focus is on methods! – Jay Mar 7 '16 at 21:08 • @Wyvern666 Unfortunately, no. I made it up myself, as far as anybody can claim to make up something like this. Maybe I'll write a citeable work myself at some point. That said, the whole corpus of work around analytical combinatorics (Flajolet, Sedgewick, and many others) is the foundation of this. They don't bother with formal semantics of "code" most of the time, but they provide the mathematics to deal with additive costs of "algorithms" in general. I honestly think the concepts laid out here are not very deep -- the mathematics you can get into are, though. – Raphael Feb 19 '17 at 20:25 • @Raphael Ok, very interesting. My other question is, i noted you talk about "additive costs", what you mean by this, and why would be a problem to work on non "additive costs". Thanks. Feb 19 '17 at 21:20 ## 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\$.

See at the bottom of my other answer.

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.
• I guess I'm not seeing how this adds anything that's useful and new, over and above other answers. The techniques are already described in other answers. This looks to me more like a comment than an answer to the question.
– D.W.
Jan 28 '15 at 18:53
• I daresay that the other answers prove that it's not an art. You may not be able to do it (i.e. the mathematics), and some creativity (as to how apply known mathematics) may be necessary even if you are, but that's true for any task. I assume we don't aspire to create new mathematics here. (In fact, this question resp. its answers were intended to demystify the whole process.)
– Raphael
Jan 28 '15 at 18:56
• @Raphael Ari is talking about coming up with a recognizable function as the bound, rather than “the number of instructions executed by the program” (which is what your answer addresses). The general case is an art — there's no algorithm that can come up with a nontrivial bound for all algorithms. The common case, however, is a set of known techniques (such as the master theorem). Jan 28 '15 at 20:04
• @Gilles If everything for which no algorithm exists were an art, craftsmen (in particular programmers) would be paid worse.
– Raphael
Jan 28 '15 at 20:28
• @AriTrachlenberg makes an important point though, there is a myriad of ways to assess an algorithm time complexity. Big O notation definitions themselves hint or directly state their theoretical nature depending on the author. "Worst case scenario" clearly leaves room open for conjecture and or new facts amongst any give N of people in the room discussing. Not to mention the very nature of asymptotic estimates being something...well unexacting. Oct 28 '15 at 2:45