Work law

The work provides a lower bound on the running time of a task-parallel computation on processors: In one step, an ideal parallel computer with processors can do at most units of work, and thus in time, it can perform at most work. Since the total work to do is , we have . Dividing by yields the work law:

.