Why Some Algorithms Divide Problems Equally: Optimizing Subproblems Sizes

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

[Prev] [Up] [Next]

Optimizing Subproblems Sizes

Having estimated the work required by a subproblem, we will now try to ﬁnd out the optimal sizes of the two subproblems. For this analysis, assume n to be even. So, the subproblems’ sizes can also be expressed as (n∕2 − a) and (n∕2 + a), for some a with 0 ≤ a < n∕2. The work required to solve the two subproblems is:

( ) ( ) w (a ) = f n-− a + f n-+ a 2 2

We assume that the work required to create the two subproblems and combine their results remains same, whatever be the two subproblems’ size distribution. So, to minimize the total work required for the size n problem, we want to pick a which minimizes w(a). Consider the value of f at (n∕2 − a) and n∕2. Due to the Mean Value Theorem from Diﬀerential Calculus, we know that there must exist b₁ in interval (n∕2 − a,n∕2) such that:

(n ) ( n ) ′ ( n (n ) ) ′ f 2- − f 2-− a = f (b1) 2-− 2-− a = f(b1)a

(1)

(Note that although n∕2 and a are integers, but b₁ need not be one.) Similarly, there must exist b₂ in interval (n∕2,n∕2 + a) such that:

( ) ( ) ( ( ) ) f n-+ a − f n- = f′(b2) n-+ a − n- = f′(b2)a 2 2 2 2

(2)

As b₁ ≤ b₂, so due to property (2) of f, f′(b₁) ≤ f′(b₂). As a ≥ 0, f′(b₁)a ≤ f′(b₂)a. Thus, equations (1) and (2) imply:

( ) ( ) ( ) ( ) f n- − f n-− a ≤ f n-+ a − f n- 2 2 2 2 ( ) ( ) ( ) ( ) ⇔ f n- + f n- ≤ f n-− a + f n-+ a = w (a) 2 2 2 2

So, we should pick a = 0 to minimize w(a). That means to choose the two subproblems sizes as n∕2 each. Note that, although we are interested in values of f only at integers, but we could bring in Diﬀerential Calculus as a useful tool.

[Prev] [Up] [Next]