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\displaystyle 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)$.

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.