Chapter 4

Divide-and-Conquer
Recall that in divide-and-conquer, we solve a problem recursively, by applying three steps
at each level of the recursion:
Divide the problem into a number of subproblems that are smaller instances of the same
problem.
Conquer the subproblems by solving them recursively. If the subproblem sizes are small
enough, however, just solve the subproblems in a straightforward manner.
Combine the solution to the subproblems into the solution for the original problem.
Recurrences:
A recurrence is a function which is defined in terms of

1. one or more base cases, and

2. itself, with smaller arguments.

Examples:
(
1 if n = 1
1. T (n) =
T (n − 1) + 1 if n > 1

The solution for the above recurrence is given by: T (n) = Θ(n)
(
1 if n = 1
2. T (n) =
2T ( n2 ) + n if n > 1

The solution for the above recurrence is given by: T (n) = Θ(n lg n)
(
0 if n = 2
3. T (n) = √
T ( n) + 1 if n > 2

The solution for the above recurrence is given by: T (n) = Θ(lg lg n)
(
1 if n = 1
4. T (n) = n 2n
T ( 3 ) + T ( 3 ) + n if n > 1

The solution for the above recurrence is given by: T (n) = Θ(n lg n)

When dealing with recurrence functions, floors and ceiling can be removed without
affecting the solution to the recurrence. There are three methods used to solve
recurrence functions:

(a) Substitution method

(b) Recursion-tree method

1
 (c) Master method

Substitution Method: The substitution method for solving recurrences entails

two steps:

(a) Guess the solution

(b) Use induction to find the constants and show that the solution works.
(
1 if n = 1
Example: Let T (n) = n
2T ( 2 ) + n if n > 1

(a) Guess: T (n) = n lg n + n

(b) Induction:
Basis: n = 1 ⇒ n lg n + n = 1 lg 1 + 1 = 1 = T (n)
Inductive step: Inductive hypothesis is that T (k) = k lg k + k for all k < n.
We will use this inductive hypothesis for T ( n2 ).
n
T (n) = 2T ( ) + n
2
n n n
= 2( lg + ) + n
2 2 2
n
= n lg + n + n
2
= n(lg n − lg 2) + n + n
= n lg n − n + n + n
= n lg n + n.

Generally, the asymptotic notation is used when dealing with recurrence relations. For
example, we could write T (n) = 2T ( n2 ) + Θ(n) for the above problem. Also, we assume
T (n) = Θ(1) for sufficiently small n. In this case the solution for the above problem
could be expressed as T (n) = Θ(n lg n). Note that since we are interested only in the
asymptotic solution to a recurrence, we don’t worry about the base case in our proofs.
We only worry about the base case if we are interested in the exact solution. One way to
find the asymptotic solution is to find the upper (O) and lower (Ω) bounds separately.
Let us see an example how this works
Example: Consider T (n) = 2T ( n2 ) + Θ(n).

1. Upper bound: If we want to show an upper bound of T (n) = 2T ( n2 ) + Θ(n), we

write T (n) ≤ 2T ( n2 ) + cn for some positive constant c.
Guess: T (n) ≤ dn lg n for some positive constant d. We are given c in the recur-
rence, and we get to choose d as any positive constant. It is OK for d to depend

2
 on c.
Substitution:
n
T (n) ≤ 2T ( ) + cn
2
n n
= 2(d lg ) + cn
2 2
n
= dn lg + cn
2
= dn lg n − dn + cn
≤ dn lg n if − dn + cn ≤ 0, d ≥ c

Therefore, T (n) = O(n lg n)

2. Lower bound: If we want to show a lower bound of T (n) = 2T ( n2 ) + Θ(n), we

write T (n) ≥ 2T ( n2 ) + cn for some positive constant c.
Guess: T (n) ≥ dn lg n for some positive constant d.
Substitution:
n
T (n) ≥ 2T ( ) + cn
2
n n
= 2(d lg ) + cn
2 2
n
= dn lg + cn
2
= dn lg n − dn + cn
≥ dn lg n if − dn + cn ≥ 0, d ≤ c

Therefore, T (n) = Ω(n lg n)

Hence, T (n) = Θ(n lg n)

Recursion Trees: are used to generate a guess. Then verify by the substitution method.
In a recursion tree, each node represents the cost of a single subproblem somewhere in
the set of recursive functions invocations. We sum the costs within each level of the tree
to obtain a set of per-level costs, and then we sum all the per-level costs to determine
the total cost of all levels of the recursion.

3
 Example: Consider the recurrence T (n) = T ( n3 ) + T ( 2n
3
) + O(n). The recursion tree
is given below:

4
 Example: Consider the recurrence T (n) = 3T ( n4 ) + Θ(n2 ). The recursion tree is
given below:

5
 Master Method: The master method is used for many divide and conquer recur-
rences of the form: T (n) = aT ( nb ) + f (n), where a ≥ 1, b > 1 are constants and f (n) > 0.
Master Theorem (Theorem 4.1 page 94)
Let a ≥ 1 and b > 1 be constants, let f (n) be a function, and let T (n) be defined on the
nonnegative integers by the recurrence
T (n) = aT ( nb ) + f (n)
where we interpret nb to mean either b nb c or d nb e. Then T (n) has the following asymptotic
bounds:

1. If f (n) = O(nlogb a− ) for some constant  > 0, then the solution is given by T (n) =
Θ(nlgb a ).

2. If f (n) = Θ(nlogb a lgk n), where k ≥ 0, then the solution is given by T (n) =
Θ(nlogb a lgk+1 n).

3. If f (n) = Ω(nlogb a+ ) for some constant  > 0, and f (n) satisfies the regularity
condition af ( nb ) ≤ cf (n) for some constant c < 1 and all sufficiently large n, then
the solution is given by T (n) = Θ(f (n))

Notice in the above theorem, we compare nlogb a vs. f (n) and we notice the following:

1. In case one, f (n) is polynomially smaller than nlgb a and the cost is dominated by
the leaves.

2. In case two, f (n) is within a polylog factor of nlogb a , but not smaller and the cost
is nlogb a lgk n at each level, and there are Θ(lg n) levels. As a simple case: Let
k = 0 ⇒ f (n) = Θ(nlogb a ) ⇒ T (n) = Θ(nlogb a lg n)

3. In case three, f (n) is polynomially greater than nlogb a and the cost is dominated
by root.

Examples:

1. T (n) = 9T ( n3 ) + n. For this recurrence, we have a = 9, b = 3, f (n) = n, and thus we

have that nlogb a = nlog3 9 = Θ(n2 ). Since f (n) = O(nlog3 9− ), where  = 1, se can
apply case 1 of the master theorem and conclude that the solution is T (n) = Θ(n2 )

2. T (n) = T ( 2n
3
) + 1. For this recurrence, we have a = 1, b = 32 , f (n) = 1, and
log 3 1
n 2 = n0 = 1. Case 2 applies, since f (n) = Θ(nlogb a ) = Θ(1), and thus the
solution to the recurrence is T (n) = Θ(lg n).

3. T (n) = 3T ( n4 ) + n lg n. For this recurrence, we have a = 3, b = 4, f (n) = n lg n, and

nlogb a = nlog4 3 = O(n0.793 ). Since f (n) = Ω(nlog4 3+ ), where  ≈ 0.2, case 3 applies

6
 if we can show that the regularity condition holds for f (n). For sufficiently large
n, we have that af ( nb ) = 3( n4 ) lg ( n4 ) ≤ ( 34 )n lg n = cf (n) for c = 34 . Consequently,
by case 3, the solution to the recurrence is T (n) = Θ(n lg n).

4. T (n) = 2T (n/2) + Θ(n). For this recurrence, we have a = 2, b = 2, f (n) = Θ(n),

and nlogb a = nlog2 2 = n. Case 2 applies, since f (n) = Θ(n), and hence, the solution
is T (n) = Θ(n lg n)

5. T (n) = 8T (n/2) + Θ(n2 ). For this recurrence, we have a = 8, b = 2, f (n) = Θ(n2 ),

and nlogb a = nlog2 8 = n3 . Since n3 is polynomially larger than f (n)(f (n) = O(n3− )
for  = 1), case 1 applies, and T (n) = Θ(n3 )

6. T (n) = 7T (n/2) + Θ(n2 ). For this recurrence, we have a = 7, b = 2, f (n) = Θ(n2 ),

and nlogb a = nlog2 7 . But, 2.80 < log2 7 < 2.81, we see that f (n) = O(nlg 7− ) for
 = 0.8 and therefore, case 1 applies. Hence, the solution is T (n) = Θ(nlg 7 )