The cost of breaking things down and putting them back together

The basic approach to solving large, complex problems is to break them down into smaller problems then re-assemble the solutions. The total cost of a solution has to account for not only the cost of solving the all the sub-problems, but also the cost of dividing the original problem into sub-problems and the cost of assembling the solutions to the sub-problems into a solution to the original problem. For example, the cost of writing a program is not simply the cost of each of the subroutines that comprise the final program. The cost has to include the cost of dividing the original task into subroutines and the cost of integrating these subroutines into the final product.

There is a theorem in computer science that quantifies the fuzzy statements above.

Let a ≥ 1 and b > 1 be constants. Let T(n) be defined on non-negative integers by the recurrence

T(n) = a T(n/b) + f(n).

In applications, T(n) is the total cost of solving a problem of size n. The recurrence relation says we have a way of breaking the original problem into b sub-problems of size n/b, each of which takes a units of work to solve. The cost of breaking the original problem into sub-problems and assembling the solutions into the final solution is described by f(n).

The theorem, which Introduction to Algorithms (ISBN 0262032937) calls the “master theorem,” says that the total cost T(n) of the solution can be bound according to three separate cases.

  1. If f(n) = O(nlogba − ε) for some constant ε > 0 then T(n) = O(nlogba).
  2. If f(n) = T(nlogba), then T(n) = T(nlogba lg(n)).
  3. If f(n) = (nlogba + ε) for some constant ε > 0, and if a f(n/b) = c f(n) for some constant c < 1 and for all sufficiently large n, then T(n) = O(f(n)).

The notation O, Ω, and Θ is explained in these notes on asymptotic order notation.

The main point here is that the term f(n), the one we tend to think less about, is the most important term in the theorem. T(n), the total time for the solution, breaks into three cases depending on whether grows at a rate slower, equal to, or faster than a multiple of nlogba.

Strictly speaking, the theorem applies to the cost (operation count) of running a program. However, you can draw an analogy from the theorem to the cost of developing a program as well. You have to consider the cost of the human subdividing the original problem (design) and the cost of making the pieces work together (integration).

3 thoughts on “The cost of breaking things down and putting them back together

  1. Master method spits out all Θ, not O. ;)

    It’s great in my algorithms class (same textbook) because it’s probably the easiest way to solve a recurrence relation. Kind of neat to see an analogy to development, and something I’ll keep in mind as I move out of school and into industry.

    Check out Akra-Bazzi for a more generalized take on the Master Method. Interesting, though probably redundant for the point you’re making.

  2. And in one further step toward the macro- end of the metaphor, the mythical man month is all about how people in large organizations drastically underestimate the problem-subdivision and re-integration bits, even if they have a decent grasp of the cost of the subroutine.

Comments are closed.