Circuit Model

The most abstract w-d model is circuit model. An algorithm is modeled as a family of directed acyclic circuits. There is a circuit for every possible size of the input. A circuit consist of nodes and arc. A node represents a basic operation, like addition of two values. For each node, there is an input of two or mode values, and one or more outputs, to other nodes sending the result. The work of the circuit is total number of nodes (also called size). The depth of the circuit is longest directed path between any two nodes (see fig.  ). The figure shows a circuit for adding 16 numbers. In this figure all arcs are directed toward the bottom. The input arcs are at the top of the figure. Each '$+$' node adds the two values that arrive on its two incoming arcs, and places the result on its outgoing arc. The sum of all of the inputs to the circuit is returned on the single output arc at the bottom.

Figure: Work-depth model.

The work in above example is 15. The depth is the number of nodes on the longest directed path from an input arc and an output arc, is 4. For a family of circuits, the work and depth are typically parameterized in terms of the number of inputs. For example, the circuit in figure  can be easily generalized to add $n$ input values for any $n$ that is a power of two. The work and depth for this family of circuits is $W(n) = n - 1$ and $D(n) = \log_2 n$.