A dependency DAG exposes two different costs of a parallel computation.

The work $W$ is the total amount of computation: the time all tasks would take if executed sequentially on one processor.

The span $S$ is the time along the longest dependency chain, also called the critical path. Even with infinitely many processors, tasks on that path must still occur in order.

For $p$ processors, the execution time $T_p$ therefore satisfies

$$T_p\ge \max!\left(\frac{W}{p},S\right).$$

Suppose two independent additions each take one time unit and their results feed one multiplication taking one unit. Then

$$W=3,\qquad S=2.$$

One processor needs three units. Two processors can perform the additions together and then the multiplication, finishing in two. No number of extra processors can reduce the time below two because the critical path remains.

The ratio

$$\frac{W}{S}$$

is the computation's average parallelism: an upper-level indication of how many processors can usefully be kept busy. Parallel performance is therefore limited not only by processor count but by the dependency structure of the algorithm itself.