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.
- If f(n) = O(nlogba – ε) for some constant ε > 0 then T(n) = O(nlogba).
- If f(n) = T(nlogba), then T(n) = T(nlogba lg(n)).
- 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).
* * *
For a daily dose of computer science and related topics, follow @CompSciFact on Twitter.