Why Some Algorithms Divide Problems Equally: Estimating Subproblem’s Work

[This page is auto-generated; please prefer to read the article’s PDF Form.]

[Prev] [Up] [Next]

Estimating Subproblem’s Work

Suppose for a given problem of size n, we know a way to divide it into two subproblems and combine their results. But we need to ﬁnd out, in what sizes should the two subproblems be created so as to minimize the total work. For this, we will ﬁrst need an estimation of how the work required by each subproblem relates to its size.

For a subproblem of size s (s ≥ 1), let f(s) denote an estimate of the amount of work required to solve it. Note that f(s) will depend upon how exactly we solve the subproblem. We can recursively solve it by dividing it into two subproblems of certain sizes (say, equal sizes), and ﬁnd an estimate based on that. As we have found above, any D2C algorithm will involve at least some work which is linear in s. Sometimes, the nature of the problem can also help us relate problem size to the work required; for example, sorting by comparison requires at least Θ(slog2(s)) comparisons.

For this discussion, we only need to ﬁnd out whether the estimated f(s) follows the below two properties or not (instead of ﬁnding the precise f(s)), for any positive integers s₁ < s₂:

f(s₁) ≤ f(s₂). That is, the work required is non-decreasing with s.
If f′ denotes the Derivative of f (Diﬀerential Calculus), then f′(s₁) ≤ f′(s₂). That is, the rate of increase of f (slope of its graph) is non-decreasing with s.

Some simple examples of such function f are (c > 0 is a constant):

f(s) = cs f′(s) = c f(s) = cs2 f′(s) = 2cs f(s) = cs log2(s) f′(s) = clog2(s)+ c∕loge(2)

[Prev] [Up] [Next]