## Execution Counts of Statements

There is another method, championed by Donald E. Knuth in his [The Art of Computer Programming](http://www-cs-faculty.stanford.edu/~uno/taocp.html) series. In contrast to [translating the whole algorithm into one formula](http://cs.stackexchange.com/a/23594/98), 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](https://en.wikipedia.org/wiki/Adjacency_list) 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](http://cs.stackexchange.com/a/23594/98).