Chapter 2

Divide and Conquer

In this chapter, we study a fundamental framework for algorithm design: Divide-and-

Conquer. The divide-and-conquer approach is directly related to recursive algorithms, but
it is much more than that.
To solve a problem of size n with the Divide-and-Conquer approach, we do the following:
• Divide the problem into sub-problems, each of size less than n.
• Conquer: Solve each sub-problem recursively (and independently of the other sub-
problems).
• Combine/Merge the solutions to the sub-problems into a solution to the original
problem.
For a given problem, We have to ask ourselves the following questions.
→ How do we divide the problem, into how many sub-problems?
→ How to combine/merge? (Most of the time, this is the most important question.)

2.1 Material from Prerequisite Courses

Obviously, you will need to remember about what a recursive algorithm is and how it works.
The tools you learnt in CSI-2101 to solve recurrences will also become very handy (the
unfolding technique and the Master Theorem).

2.1.1 Merge Sort

The golden example for the divide-and-conquer approach is Merge Sort. You studied this
algorithm in CSI-2101 and CSI-2110. Let us quickly review this algorithm. Then we will
make some comments about how to analyse the running time of recursive algorithms.

37
Consider the following pseudo-code for Merge Sort.

Algorithm 12 MergeSort(A[1..n])
Input: An array A[1..n] with n numbers.
Output: The array A sorted.
1: if n = 1 then
2: return A
3: else
4: m = ↑n/2↓
5: Aω =MergeSort(A[1..m])
6: Ar =MergeSort(A[(m + 1)..n])
7: Merge Aω and Ar into one single sorted array B.
8: return B
9: end if

Here is the trace of this algorithm on a small input. Consider the following input.

A[1..8] = [5, 9, 1, 5, 8, 4, 20, 0]

First, the algorithm recursively sorts A[1..4] = [5, 9, 1, 5]. Then, the algorithm recursively
sorts A[5..8] = [8, 4, 20, 0]. We get

Aω = [1, 5, 5, 9] et Ar = [0, 4, 8, 20].

Then, the algorithm “merges Aω and Ar into one single sorted array B.” How does this merge
step work? We look at the first element in Aω and the first element in Ar and we transfert
the smallest of the two into B. Then we repeat. Here is what we get with our example.
Aω Ar B
[1, 5, 5, 9] [0, 4, 8, 20] B =[]
[1, 5, 5, 9] [4, 8, 20] B = [0]
[5, 5, 9] [4, 8, 20] B = [0, 1]
[5, 5, 9] [8, 20] B = [0, 1, 4]
[5, 9] [8, 20] B = [0, 1, 4, 5]
[9] [8, 20] B = [0, 1, 4, 5, 5]
[9] [20] B = [0, 1, 4, 5, 5, 8]
[] [20] B = [0, 1, 4, 5, 5, 8, 9]
[] [] B = [0, 1, 4, 5, 5, 8, 9, 20]
In total, to merge Aω and Ar , MergeSort performs n ↔ 1 comparisons (there are n numbers
to transfer into B). And we must not forget that right at the beginning, the algorithm
performs one comparison to decide whether n = 1. As such, we have a total of n comparisons,
excluding the recursive calls to MergeSort.

38
Let us now figure out the number of comparisons performed by MergeSort. Let T (n) be the
number of comparisons performed by MergeSort on an input (an array) of size n. We have

T (n) = T (m) + T (n ↔ m) + n
= T (↑n/2↓) + T (↗n/2↘) + n.

The presence of the floor function ↑·↓ and the ceiling function ↗·↘ is a little annoying. If n
was a power of two, we could write

T (n) = 2 T (n/2) + n,

which is much easier to handle. We can, for instance use unfolding to solve this recurrence.
Indeed, if n = 2k for an integer k ≃ 1, then

T (n) = 2 T (n/2) + n
! ! " "
n/2 n
= 2 2T + +n
2 2
# $
= 22 T n/22 + 2n
! ! " "
2 n/22 n
= 2 2T + 2 + 2n
2 2
# $
= 23 T n/23 + 3n
! ! " "
3 n/23 n
= 2 2T + 3 + 3n
2 2
4
# 4
$
= 2 T n/2 + 4n
..
.
# $
= 2k T n/2k + kn (2.1)
= n T (n/n) + n log2 (n) since n = 2k ,
= n + n log2 (n) since f (n/n) = f (1) = 1,
# $
= n 1 + log2 (n)
= O(n log(n)). (2.2)

What do we do now if n is not a power of 2? Exercise 13 asks you to prove (by induction
on n) that
T (n) = T (↑n/2↓) + T (↗n/2↘) + n
solves to T (n) = O(n log(n)) in general.
When we analyze the running time of a recursive algorithm, most of the time, we will have
to deal with expressions like “T (↑n/2↓)” or “T (↗n/2↘)”. If it turns out that n is even, then
we can forget about the floor/ceiling functions. Otherwise, what do we do? We do not want

39
to have to go through a proof by induction every time1 . It turns out there is a theorem due
to Akra-Bazzi which says... very roughly speaking... that we do not need to worry about
floor/ceiling function in these recursive equations2 . We can simply ignore them.

2.2 Finding a Peak

In this section, we study the problem of finding a peak (or a local maximum) in an array.

2.2.1 Finding a Peak in a One-Dimensional Array

In an array A[1..n] of n numbers, the entry A[i] is a peak if it is greater than or equal to all
of its neighbours in A. What does this mean? What do we mean by “all of its neighbours”?

• If n = 1, then A[1] is the only element. As such, it does not have any neighbour. By
default, we say that A[1] is a peak.

• If n ≃ 2, then A[1] has exactly one neighbour, namely A[2]. The entry A[n] also has
exactly one neighbour, namely A[n ↔ 1]. So A[1] is a peak if A[1] ≃ A[2] and A[n] is a
peak if A[n] ≃ A[n ↔ 1].

• If n ≃ 3, then for all 1 < i < n, A[i] has exactly two neighbours, namely A[i ↔ 1] and
A[i + 1]. So A[i] is a peak if A[i] ≃ A[i ↔ 1] and A[i] ≃ A[i + 1].

Be careful! A peak is an entry of the array, not the index of this entry.
1
Such inductive arguments involving floor/ceiling functions can be very tedious.
2
The exact statement of Akra-Bazzi theorem is actually much more involved, but this is beyond the
scope of this course. The algorithms and the recursive equations we will encounter this semester are “simple
enough” for us to ignore floor/ceiling functions and proceed with unfolding, or use the Master Theorem as
we will discuss later.

40
In the following array,
A = [1, 2, 2, 3, ↔5, 7, 8, 11]
the peaks are A[2] = 2, A[4] = 3 and A[8] = 11. In the following array,

A = [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]

all entries are peaks!

The problem we want to solve in this section is the following.
INPUT: An array A[1..n] of n numbers.
OUTPUT: None if there is no peak in A, a peak if there is at least one peak in A.
What would be a brute force solution for this problem? We could scan A[1..n] from index
1 to index n. For each entry A[i], we compare it to all of its neighbours. If it is a peak, we
return it and we stop. If it is not a peak, we keep scanning. If we reach the end of the index
and no peak was found, we return None. What is the running time of this algorithm? For
each entry in A[1..n], we do the following.
• We do at most 2 comparisons.
• We increment an index to move on to the next element in A.
So the running time of this algorithm is O(n) in the worst case.
Can we do better? Before answering this question, there is an important observation we
need to make. If we think about it, there is always at least one peak in any one-dimensional
array.
Lemma 1. Let A[1..n] be an array, where n ≃ 1. Then A contains at least one peak.

Proof. If n = 1, then A[1] is, by default, a peak as we already discussed. For the rest of the
proof, assume n > 1.
Let 1 ⇐ k ⇐ n be such that A[k] is maximum in A. Since A[k] is maximum, then it is larger
than or equal to its neighbour(s). Therefore, A[k] is a peak.
So we can reformulate the problem as:

INPUT: An array A[1..n] of n numbers.

OUTPUT: A peak in A.

Is there a faster solution than the brute force approach? Let us try to use the divide-and-
conquer approach! Think about binary search... what can we learn from the element in the
middle of the array? Consider the following array.

A = [1, 2, 2, 3, ↔5, ↔6, 8, 11, 9]

41
The middle element is A[5] = ↔5, which is not a peak since A[4] = 3 > ↔5 = A[5].
Intuitively, since the left neighbour of A[5] is larger than A[5], it seems promising to recurse
on the left part of A, i.e., to recurse on A[1..5].

A = [1, 2, 2, 3, ↔5, ↔6, 8, 11, 9]

In A[1..5], the middle element is A[3] = 2, which is not a peak since A[4] = 3 > 2 = A[3].
We then recurse on the right part of A[1..5], i.e., on A[3..5].

A = [1, 2,2, 3, ↔5, ↔6, 8, 11, 9]

In A[3..5], the middle element is A[4] = 3, which is a peak, so we return 3.

We have to clarify what is the base case of this recursion. This is simple: if n ⇐ 2, then
we scan the array to find a peak. This takes O(1) time. Here is the pseudo-code of this
algorithm.

Algorithm 13 1D-Peak
Input: An array A[1..n] of n numbers.
Output: A peak in A.
1: if n ⇐ 2 then
2: if n = 1 then
3: return A[1]
4: else if A[1] ≃ A[2] then
5: return A[1]
6: else
7: return A[2]
8: end if
9: else
10: m = ↑(n + 1)/2↓
11: if A[m] ≃ A[m ↔ 1] and A[m] ≃ A[m + 1] then
12: return A[m]
13: else if A[m] < A[m ↔ 1] then
14: Call 1D-Peak(A[1..m])
15: else
16: Call 1D-Peak(A[m..n])
17: end if
18: end if

We now have to analyse the running time of this algorithm and we have to explain why this
algorithm is correct. Let us start with the analysis of the running time. Let T (n) be the
running time of 1D-Peak on an input of size n. If n ⇐ 2, then T (n) ⇐ 7. Otherwise, we have

T (n) ⇐ T (n/2) + 16.

42
Let us unfold this equation. Therefore, assume n = 2k for an integer k. We find
T (n) ⇐ T (n/2) + 16
! ! " "
n/2
⇐ T + 16 + 16
2
= T (n/22 ) + 2 · 16
! ! " "
n/22
⇐ T + 16 + 2 · 16
2
= T (n/23 ) + 3 · 16
! ! " "
n/23
⇐ T + 16 + 3 · 16
2
= T (n/24 ) + 4 · 16
..
.
= T (n/2k→1 ) + (k ↔ 1) · 16
= T (2) + (k ↔ 1) · 16
⇐ 7 + 16(log2 (n) ↔ 1)
= ↔9 + 16 log2 (n)
= O(log(n)).

Why is this algorithm correct?

Lemma 2. If 1D-Peak makes a recursive call on a sub-array A↑ of A[1..n], then A↑ contains
a peak of A[1..n].

Proof. By the definition of 1D-Peak, if 1D-Peak makes a recursive call, then n ≃ 3. There-
fore, m = ↑(n + 1)/2↓ satisfies 2 ⇐ m ⇐ n ↔ 1, from which 1 ⇐ m ↔ 1 ⇐ n ↔ 2 and
3 ⇐ m + 1 ⇐ n. In other words, the neighbours of A[m] are well defined.
Assume 1D-Peak makes a recursive call on the left sub-array A↑ = A[1..m] of A[1..n]. Then we
have A[m] < A[m↔1] (and A[m↔1] is well-defined since m↔1 ≃ 1). Consider the maximum
element M of A↑ . Since M is maximum in A↑ , we have M ≃ A[m ↔ 1] > A[m]. Therefore,
M ⇒= A[m], from which M belongs to A↑ together with all of its neighbours. Moreover, since
M is maximum, M is greater than or equal to all of its neighbours. Therefore, M is a peak
both in A↑ and in A.
If 1D-Peak makes a recursive call on the right sub-array A[m..n] of A, we can make a
symmetric argument.
The 1D-Peak algorithm always makes a recursive call on a sub-array A↑ of A that is strictly
smaller than A. Therefore, either it returns a peak of A↑ (which is a peak of A by the previous
lemma) or it reaches the base case. By the definition of 1D-Peak, if 1D-Peak reaches the
base case, then it returns a peak (which is a peak of A by the previous lemma).

43
2.2.2 Finding a Peak in a Two-Dimensional Array

A peak in a 2D-array is defined in a similar way as in 1D. To simplify the discussion,

assume that all 2D-arrays are square arrays A[1..n, 1..n] for some integer n ≃ 1. In an array
A[1..n, 1..n], a peak is a number A[i, j] that is greater than or equal to all of its neighbours
in A. What do we mean by “all of its neighbours”? For 2D-arrays we consider the leftward,
rightward, upward and downward neighbours.

44
 1 n
1

up

left A[i, j] right

down

Boundary and corner cells

Boundary cells

Interior cells

If a number A[i, j] is on one of the four corners of the square3 , then A[i, j] has two neighbours.
If A[i, j] is on one of the four edges of the square but not on a corner4 , then A[i, j] has three
neighbours. We refer to the set of all edge cells as boundary cells. The cells that are not on
the boundary are referred to as interior cells.
And otherwise, A[i, j] has four neighbours. We also have to be careful about the border case
where n = 1. In this case, A[1, 1] has no neighbour and is considered to be a 2D-peak by
default.
In the following table, the peaks are the numbers in red.

1 2 3 4 5 6 7
3 0 0 0 0 0 6
5 0 0 0 0 0 9
7 0 0 8 0 0 10
9 0 0 0 0 1 12
9 0 0 0 0 0 11
10 9 8 7 8 9 10

In this section, we want to solve the following problem.

3
In other words, i and j satisfy one of the following conditions: (1) i = j = 1, (2) i = 1 and j = n, (3)
i = n and j = 1, or (4) i = j = n.
4
In other words, i and j satisfy one of the following conditions: (1) i = 1, j ⇒= 1 and j ⇒= n, (2) i = n,
j ⇒= 1 and j ⇒= n, (3) i ⇒= 1, i ⇒= n and j = 1, or (4) i ⇒= 1, i ⇒= n and j = n.

45
 INPUT: A 2D-array of numbers A[1..n, 1..n], where n ≃ 1.
OUTPUT: “NONE” if there is no peak in A, a peak if there is at least one peak in A.

Like in the 1D-case, we have the following property.

Lemma 3. Let A[1..n, 1..n] be a 2D-array of numbers. Then A contains at least one peak.

Proof. If n = 1, then A[1, 1] is, by default, a peak as we already discussed. For the rest of
the proof, assume n > 1.

Let 1 ⇐ k, ω ⇐ n be such that A[k, ω] is maximum in A. Since A[k, ω] is maximum, then it is

larger than or equal to all of its neighbours. Therefore, A[k, ω] is a peak.

As such, we can reformulate the problem as:

INPUT: A 2D-array A[1..n, 1..n] of numbers.

OUTPUT: a peak in A.

Can you think of a brute force solution for this problem? What is the running time you
get? Can we do better? How can we solve this problem e!ciently? Let us try to use the
divide-and-conquer approach... but how do we split the problem into sub-problems??

Does it help to look at the center element?

7 8 9 11 12 13 14 2 0
6 7 8 10 10 11 12 0 1
5 6 7 9 8 10 11 1 2
4 5 6 8 9 8 10 2 0
3 4 5 6 8 7 9 0 1
2 3 4 5 6 6 8 1 2
1 2 3 4 5 5 7 2 0
2 3 0 1 2 3 4 0 1
3 0 1 2 3 4 0 1 2

This enables us to decide whether or not the center element is a peak, but then what?

Instead, let us try to look at then center column.

46
 7 8 9 10 12 13 10 2 0
6 7 8 11 13 14 12 0 1
5 6 7 9 9 15 11 1 2
4 5 6 8 8 16 10 2 0
3 4 5 6 8 7 9 0 1
2 3 4 5 6 6 8 1 2
1 2 3 4 5 5 7 2 0
2 3 0 1 2 3 4 0 1
3 0 1 2 3 4 0 1 2

It seems reasonable to consider the maximum element m of this column and to see whether
it is a peak. If m is a peak, then we are done. Otherwise, at least one of the leftward or the
rightward neighbour of m has to be strictly bigger.

7 8 9 10 12 13 10 2 0 7 8 9 10 12 13 10 2 0
6 7 8 11 13 14 12 0 1 6 7 8 11 13 14 12 0 1
5 6 7 9 9 15 11 1 2 5 6 7 9 9 15 11 1 2
4 5 6 8 8 16 10 2 0 4 5 6 8 8 16 10 2 0
3 4 5 6 8 7 9 0 1 3 4 5 6 8 7 9 0 1
2 3 4 5 6 6 8 1 2 2 3 4 5 6 6 8 1 2
1 2 3 4 5 5 7 2 0 1 2 3 4 5 5 7 2 0
2 3 0 1 2 3 4 0 1 2 3 0 1 2 3 4 0 1
3 0 1 2 3 4 0 1 2 3 0 1 2 3 4 0 1 2

So we recurse on the side where we can find a strictly bigger neighbour of m. (If both
the leftward and the rightward neighbours are strictly bigger than m, then we can pick
arbitrarily.)

47
 7 8 9 10 12 13 10 2 0 7 8 9 10 12 13 10 2 0
6 7 8 11 13 14 12 0 1 6 7 8 11 13 14 12 0 1
5 6 7 9 9 15 11 1 2 5 6 7 9 9 15 11 1 2
4 5 6 8 8 16 10 2 0 4 5 6 8 8 16 10 2 0
3 4 5 6 8 7 9 0 1 3 4 5 6 8 7 9 0 1
2 3 4 5 6 6 8 1 2 2 3 4 5 6 6 8 1 2
1 2 3 4 5 5 7 2 0 1 2 3 4 5 5 7 2 0
2 3 0 1 2 3 4 0 1 2 3 0 1 2 3 4 0 1
3 0 1 2 3 4 0 1 2 3 0 1 2 3 4 0 1 2

7 8 9 10 12 13 10 2 0 7 8 9 10 12 13 10 2 0
6 7 8 11 13 14 12 0 1 6 7 8 11 13 14 12 0 1
5 6 7 9 9 15 11 1 2 5 6 7 9 9 15 11 1 2
4 5 6 8 8 16 10 2 0 4 5 6 8 8 16 10 2 0
3 4 5 6 8 7 9 0 1 3 4 5 6 8 7 9 0 1
2 3 4 5 6 6 8 1 2 2 3 4 5 6 6 8 1 2
1 2 3 4 5 5 7 2 0 1 2 3 4 5 5 7 2 0
2 3 0 1 2 3 4 0 1 2 3 0 1 2 3 4 0 1
3 0 1 2 3 4 0 1 2 3 0 1 2 3 4 0 1 2

And we recurse once more

7 8 9 10 12 13 10 2 0 7 8 9 10 12 13 10 2 0
6 7 8 11 13 14 12 0 1 6 7 8 11 13 14 12 0 1
5 6 7 9 9 15 11 1 2 5 6 7 9 9 15 11 1 2
4 5 6 8 8 16 10 2 0 4 5 6 8 8 16 10 2 0
3 4 5 6 8 7 9 0 1 3 4 5 6 8 7 9 0 1
2 3 4 5 6 6 8 1 2 2 3 4 5 6 6 8 1 2
1 2 3 4 5 5 7 2 0 1 2 3 4 5 5 7 2 0
2 3 0 1 2 3 4 0 1 2 3 0 1 2 3 4 0 1
3 0 1 2 3 4 0 1 2 3 0 1 2 3 4 0 1 2

until we find a peak.

48
 7 8 9 10 12 13 10 2 0
6 7 8 11 13 14 12 0 1
5 6 7 9 9 15 11 1 2
4 5 6 8 8 16 10 2 0
3 4 5 6 8 7 9 0 1
2 3 4 5 6 6 8 1 2
1 2 3 4 5 5 7 2 0
2 3 0 1 2 3 4 0 1
3 0 1 2 3 4 0 1 2

We can argue that this approach is indeed correct. And we can show that it solves the
problem in O(n log(n)) time (refer to Exercise 4).

Can we do better?

Let us try the following approach. In order to simplify the discussion, we now assume that
n = 2k + 1 for an integer k ≃ 1 (everything works if n is an arbitrary integer, this is only
to simplify the discussion). Let us consider a window frame that we superimpose onto the
array. The window frame of A corresponds to the union of the three rows 1, 2k→1 + 1, and
n, together with the three columns 1, 2k→1 + 1, and n.

1 2k 1
+1 n 1 5 9
1 1

2k 1
+1 5

n 9

n = 2k + 1 n = 23 + 1
window frame of a 2D-array

We start by scanning all the numbers in this window frame and we search for a maximum
element m. Let us say that the maximum element is A[i, j] = m. Since this maximum is
part of the window frame, then i ⇑ {1, 2k→1 + 1, n} or j ⇑ {1, 2k→1 + 1, n}.

49
 1 2k 1
+1 n 1 5 9
1 1 7 6 12 2 4 7 0 5 6
1 5 7
1 11 0
2 4 8
2k 1
+1 m 5 0 0 1 6 5 4 11 12 7
3 0 9
7 0 1
3 9 2
n 9 5 5 5 0 10 11 0 10 6

n = 2k + 1 n = 23 + 1
⇥ ⇤
A 2k 1
+ 1, n 1 =m A[5, 8] = 12

If A[i, j] is a peak, then we are done!

1 2k 1
+1 n 1 5 9
1 1 7 6 12 2 4 7 0 5 6
1 5 7
1 11 0
< m 2 4 2 8
2k 1
+1 m 5 0 0 1 6 5 4 11 12 7
 m 3 0 12 9
7 0 1
3 9 2
n 9 5 5 5 0 10 11 0 10 6

n = 2k + 1 n = 23 + 1
⇥ ⇤
A 2k 1
+ 1, n 1 =m A[5, 8] = 12

m is a peak 12 is a peak

Otherwise, what do we do?

50
 1 2k 1
+1 n 1 5 9
1 1 7 6 12 2 4 7 0 5 6
1 5 7
1 11 0
< m 2 4 2 8
k 1
2 +1 m 5 0 0 1 6 5 4 11 12 7
> m 3 0 13 9
7 0 1
3 9 2
n 9 5 5 5 0 10 11 0 10 6

n = 2k + 1 n = 23 + 1
⇥ ⇤
A 2k 1
+ 1, n 1 =m A[5, 8] = 12

m is not a peak 12 is not a peak

If A[i, j] = m is not a peak, then there must be a neighbour5 A[i↑ , j ↑ ] of A[i, j] that is
strictly bigger than A[i, j], i.e., A[i↑ , j ↑ ] > A[i, j]. The neighbour A[i↑ , j ↑ ] cannot be part of
the window frame of A, otherwise this would contradict the fact that A[i, j] is a maximum
element
# k→1in the$window
# k→1frame$ of A. As such, A[i , j ] is in the interior of one of the following
↑ ↑

four 2 +1 ⇓ 2 + 1 sub-arrays

% # $ # $&
At,ω = A 1.. 2k→1 + 1 , 1.. 2k→1 + 1 ,
% # $ # $ &
At,r = A 1.. 2k→1 + 1 , 2k→1 + 1 ..n ,
%# $ # $&
Ab,ω = A 2k→1 + 1 ..n, 1.. 2k→1 + 1 ,
%# $ # $ &
Ab,r = A 2k→1 + 1 ..n, 2k→1 + 1 ..n .

Let A↑ ⇑ {At,ω , At,r , Ab,ω , Ab,r } be the sub-array of A such that A[i↑ , j ↑ ] is in the interior of A↑ .
We then recurse on A↑ .

5
The possible neighbours of A[i, j] are A[i ↔ 1, j], A[i + 1, j], A[i, j ↔ 1] and A[i, j + 1], depending on
whether or not A[i, j] is on the boundary or on a corner of A.

51
 1 2k 1
+1 n 1 5 9
1 1 7 6 12 2 4 7 0 5 6
1 5 7
1 11 0
< m 2 4 2 8
2k 1
+1 m 5 0 0 1 6 5 4 11 12 7
> m 3 0 13 9
7 0 1
3 9 2
n 9 5 5 5 0 10 11 0 10 6

n = 2k + 1 n = 23 + 1
⇥ ⇤
A 2k 1
+ 1, n 1 =m A[5, 8] = 12
⇥ ⇤
A 2k 1
+ 2, n 1 >m A[6, 8] = 12
We recurse on A0 = Ab,r . We recurse on A0 = Ab,r .

And when do we stop the recursion? Either when we find a peak or when n = 21 + 1 = 3. If
we reach the base case where n = 3, the window frame is equal to the entire array (do you
see why?) In such a case, we simply scan all the numbers in the array to find a peak. As we
scan the array, we compare each number to all of its neighbours to see whether or not it is
a peak.
We can summarize this algorithm in the following way. To simplify the presentation of the
pseudo-code, we still assume that n = 2k + 1 for an integer k ≃ 1.

Algorithm 2D-P eak(A[1..n, 1..n])

Input: A 2D-array A[1..n, 1..n] such that n = 2k + 1 for an integer k ≃ 1.
Output: A peak in A.
1: if n = 3 then
2: Scan A to find a peak and return it.
3: else
4: Scan the window frame of A to find a maximum element A[i, j].
5: if A[i, j] is a peak then
6: return A[i, j]
7: else
8: Let A[i↑ , j ↑ ] be a neighbour of A[i, j] such that A[i↑ , j ↑ ] > A[i, j].
9: Let A↑ ⇑ {At,ω , At,r , Ab,ω , Ab,r } be the sub-array of A which contains A[i↑ , j ↑ ] in its
interior.
10: Call 2D-P eak(A↑ ).
11: end if
12: end if

52
We now have to analyse the running time of this algorithm and we have to explain why this
algorithm is correct. Let us start with the analysis of the running time. The pseudo-code
we presented for 2D-Peak is somehow high level. Except for Lines 1 and 10, some details
are missing. Let us discuss these missing details.
Line 2: In this case, A is 3 ⇓ 3. As such, A contains 9 numbers. Each of these 9 numbers
must be compared to at most four other numbers (their neighbours). For instance, for
A[2, 2], we need to evaluate the following Boolean expression

A[2, 2] ≃ A[1, 2] ⇔ A[2, 2] ≃ A[2, 1] ⇔ A[2, 2] ≃ A[2, 3] ⇔ A[2, 2] ≃ A[3, 2].

Depending on how we analyse it, this Boolean expression requires up to 16 steps. For
the other elements of A, the Boolean expression is made of 2 or 3 comparisons only.
As such, this line can be executed in less than 9 · 16 = 151 steps.
Line 4: This requires scanning 3 rows and 3 columns to find the maximum element. Thus,
this line takes at most 6n steps.
Line 5: This can be done using a simple Boolean expression which requires less than 16
steps.
Line 8: This can be done using a simple Boolean expression which requires less than 16
steps.
Line 9: This can also be done using a simple Boolean expression which requires less than
16 steps.
So in total, we can write T (3) ⇐ 151 and

T (n) ⇐ T (n/2) + 6n + 50. (2.3)

Depending on how we analyze the pseudo-code of 2D-peak, we might get an additive constant
di"erent than “50”, but what really matters is that it is an additive constant. Before we
proceed with the unfolding, let us clarify something. We made the assumption that n = 2k +1
for an integer k ≃ 1. As we already explained, the only reason why we made this assumption
was to simplify the presentation of the algorithm and the presentation of the pseudo-code.
If no assumption had been made on n, we would get the same recursive equation (2.3) for
the running time of 2D-peak. Moreover, for n = 1, we would get T (1) = 1. Indeed, if a
2D-array is 1 ⇓ 1, then the only element in the array is a peak by default. So we would just
return this element.
Now, we have a function T (n) which satisfies (2.3) and we want to know how fast T (n)
grows. We can forget about the algorithm. This is a purely mathematical question. And
how do we answer it? Using unfolding! And for unfolding, as usual, we are going to assume
that n is a power of 2. Assume n = 2ω for an integer ω ≃ 1. We find

T (n) ⇐ T (n/2) + 6n + 50

53
 ! ! " "
n/2
⇐ T + 6(n/2) + 50 + 6n + 50
2
! "
2 1
= T (n/2 ) + 6n 1 + + 2 · 50
2
! ! " " ! "
n/22 2 1
⇐ T + 6(n/2 ) + 50 + 6n 1 + + 2 · 50
2 2
! "
3 1 1
= T (n/2 ) + 6n 1 + + + 3 · 50
2 4
! ! " " ! "
n/23 3 1 1
⇐ T + 6(n/2 ) + 50 + 6n 1 + + + 3 · 50
2 2 4
! "
4 1 1 1
= T (n/2 ) + 6n 1 + + + + 4 · 50
2 4 8
..
.
ω→1
'
ω 1
= T (n/2 ) + 6n + ω · 50
i=0
2i
! "
ω 2
= T (n/2 ) + 6n 2 ↔ ω + ω · 50
2
! "
2
= T (n/n) + 6n 2 ↔ + log2 (n) · 50
n
= 1 + 12n ↔ 12 + log2 (n) · 50
= O(n).
In conclusion, 2D-P eak takes O(n) time.
Now that the unfolding is done, let us get back to our assumption that n = 2k + 1 for an
integer k. Why is this algorithm# correct?
$ First
# notice
$ that since n = 2k + 1, then if we
recurse on A↑ , then A↑ has size 2k→1 + 1 ⇓ 2k→1 + 1 , which satisfies the precondition of
the algorithm.
Lemma 4. If 2D-Peak makes a recursive call on a sub-array A↑ of A[1..n, 1..n], then A↑
contains a peak of A[1..n, 1..n].

Proof. By the definition of 2D-Peak, if 2D-Peak makes a recursive call, then n ≃ 5 (remember
our assumption: n = 2k + 1 for an integer k ≃ 1).
First consider the case where 2D-Peak makes a recursive call on A↑ = At,ω . Let A[i, j] be
the maximum element in the window frame of A and let A[i↑ , j ↑ ] be the neighbour of A[i, j]
such that A[i↑ , j ↑ ] > A[i, j] and A[i↑ , j ↑ ] is in the interior of A↑ . Now let M be the maximum
element of A↑ .
Observe that M does not belong to the boundary of A↑ . Otherwise, it would belong to the
window frame of A. This would contradict the fact that A[i, j] is a maximum element in the

54
window frame of A. Therefore, all the neighbours of M in A are also in A↑ . Moreover, we
have M ≃ A[i↑ , j ↑ ] > A[i, j]. Therefore, M is a peak both in A↑ and in A.
If 2D-Peak makes a recursive call on At,r , Ab,ω or Ab,r , the argument is the same.
The 2D-Peak algorithm always makes a recursive call on a sub-array A↑ of A that is strictly
smaller than A. Therefore, either it returns a peak of A↑ (which is a peak of A by the previous
lemma) or it reaches the base case. By the definition of 2D-Peak, if 2D-Peak reaches the
base case, then it returns a peak (which is a peak of A by the previous lemma).

2.3 The Strassen Algorithm for Matrix Multiplication

In this section, we present Strassen’s algorithm to multiply two matrices. But let us first
remind what matrix multiplication is about. Take two n ⇓ n matrices A and B.
   
a11 a12 · · · a1n b11 b12 · · · b1n
 a21 a22 · · · a2n   b21 b22 · · · b2n 
   
A =  .. .. . . ..  B =  .. .. . . .. 
 . . . .   . . . . 
an,1 an2 · · · ann bn,1 bn2 · · · bnn

The product of A and B, say C = AB is defined by

 
c11 c12 · · · c1n
 c21 c22 · · · c2n 
 
C =  .. .. . . ..  ,
 . . . . 
cn,1 cn2 · · · cnn

where n
'
cij = aik bkj
k=1

for all 1 ⇐ i ⇐ n and all 1 ⇐ j ⇐ n.

Here is an example where we multiply two 3 ⇓ 3 matrices.
    
1 0 ↔1 4 0 7 ↔2 ↔1 8
0 2 3  ↔2 1 0  =  14 5 ↔3
1 5 0 6 1 ↔1 ↔6 5 7

For instance, 8 = 1 · 7 + 0 · 0 + (↔1) · (↔1) and 14 = 0 · 4 + 2 · (↔2) + 3 · 6.

We can easily translate the definition of matrix multiplication into an algorithm.
Input: Two square matrices An↓n and Bn↓n .
Output: AB.
1: Initialize matrix Cn↓n

55
 2: for i = 1 to n do
3: for j = 1 to n do
4: cij = 0
5: for k = 1 to n do
6: cij = cij + aik bkj
7: end for
8: end for
9: end for
10: return C

The running time of this algorithm is

n '
' n '
n
# $
T (n) = 1 = ! n3 .
i=1 j=1 k=1

How can we divide and conquer? Assume n = 2k and observe the following recursive struc-
ture.     
1 0 ↔1 2 0 1 2 3 9 3 ↔3 1
3 1 1 1 ↔2 1 ↔1 1  4 5 4 9
  = 
0 0 0 1   1 0 1 0  5 1 ↔2 ↔1
2 4 7 1 5 1 ↔2 ↔1 4 7 5 9
! " ! " ! " ! "  ! " ! "
1 0 ↔1 2 0 1 2 3 9 3 ↔3 1
 3  
1" !1 1"   !↔2 1" ! ↔1  
1 "  ! 4 5" ! 4 9 "
! = 
 0 0 0 1  1 0 1 0   5 1 ↔2 ↔1 
2 4 7 1 5 1 ↔2 ↔1 4 7 5 9
In general, we have ! " ! "
A11 A12 B11 B12
A= B=
A21 A22 B21 B22
! " ! "! "
C11 C12 A11 A12 B11 B12
C= = ,
C21 C22 A21 A22 B21 B22
where
C11 = A11 B11 + A12 B21 ,
C12 = A11 B12 + A12 B22 ,
C21 = A21 B11 + A22 B21 ,
C22 = A21 B12 + A22 B22 .

We can easily turn this observation into a recursive algorithm. If T (n) is the running time
of this recursive algorithm, then we get
T (n) = 8 T (n/2) + 4 (n/2)2 = 8 T (n/2) + n2 .

56
So? How good is this? Let us unfold this recurrence. Assume n = 2k for an integer k, and
observe that T (1) = 1.

T (n) = 8 T (n/2) + n2
! ! " . /"
n/2 n 2
= 8 8T + + n2
2 2
# $
= 82 T n/22 + 2n2 + n2
! ! " . /"
2 n/22 n 2
= 8 8T + 2 + 2n2 + n2
2 2
# $
= 83 T n/23 + 4n2 + 2n2 + n2
! ! " . /"
3 n/23 n 2
= 8 8T + 3 + 4n2 + 2n2 + n2
2 2
# $
= 84 T n/24 + 8n2 + 4n2 + 2n2 + n2
..
.
# $
= 8k T n/2k + 2k→1 n2 + ... + 22 n2 + 21 n2 + 20 n2
k→1
'
# $3 # $
= 2k T n/2k + n2 2i

3 2
# k
$i=0
= n T (1) + n 2 ↔ 1
# $
= n3 T (1) + n2 n ↔ 1
= 2n3 ↔ n2

Unfortunately, this recursive approach did not work. From here, we have two options: the
divide-and-conquer approach does not work, or it does work, but we need to find a better
trick. And since we are in a chapter about divide-and-conquer, then, most likely, there is a
way to apply this technique here.
Volker Strassen in 1969 figured out how to do that. Here is how Strassen’s algorithm works.
Let us define the following ten matrices.

S1 = B12 ↔ B22
S2 = A11 + A12
S3 = A21 + A22
S4 = B21 ↔ B11
S5 = A11 + A22
S6 = B11 + B22
S7 = A12 ↔ A22
S8 = B21 + B22
S9 = A11 ↔ A21

57
 S10 = B11 + B12

Why not?! And since we are having fun, let us define the following seven matrices (it’s free!)

P1 = A11 S1 = A11 B12 ↔ A11 B22

P2 = S2 B22 = A11 B22 + A12 B22
P3 = S3 B11 = A21 B11 + A22 B11
P4 = A22 S4 = A22 B21 ↔ A22 B11
P5 = S5 S6 = A11 B11 + A11 B22 + A22 B11 + A22 B22
P6 = S7 S8 = A12 B21 + A12 B22 ↔ A22 B21 ↔ A22 B22
P7 = S9 S10 = A11 B11 + A11 B12 ↔ A21 B11 ↔ A21 B12

And finally, look at the following.

P 5 + P4 ↔ P2 + P6
= A11 B11 + A11 B22 + A22 B11 + A22 B22
↔ A22 B11 + A22 B21
↔ A11 B22 ↔ A12 B22
↔ A22 B22 ↔ A22 B21 + A12 B22 + A12 B21
= A11 B11 + A12 B21
= C11
It turns out that C11 = P5 + P4 ↔ P2 + P6 . And what is C11 again? If you remember, it is
one of the pieces of C = AB! But that’s not the end of the story. We have

C11 = P5 + P4 ↔ P2 + P6 ,
C12 = P1 + P2 ,
C21 = P3 + P 4 ,
C22 = P5 + P 1 ↔ P3 ↔ P7 .

To compute all the Si ’s, we need to perform 10 additions/subtractions on n2 ⇓ n2 matrices.

Then, to compute all the Pi ’s, we need to perform 7 matrix multiplications on n2 ⇓ n2 matrices.
Finally, to compute the Ci,j ’s, we need to perform 8 additions/subtractions on n2 ⇓ n2 matrices.
Therefore, in total, we have

T (n) = 7 T (n/2) + 18(n/2)2 = 7 T (n/2) + (9/2)n2 .

Let us unfold this recurrence. Assume n = 2k for an integer k, and observe that T (1) = 1.
We find
9
T (n) = 7 T (n/2) + n2
! ! 2" "
n/2 9 . n /2 9
= 7 7T + + n2
2 2 2 2

58
 # $ 7 9 9
= 72 T n/22 + · n2 + n2
! ! 4" 2 2 "
n/2 2
9 n /2
. 7 9 9
= 72 7 T + 2
+ · n2 + n2
2 2 2 4 2 2
! "2
# $ 7 9 2 7 9 2 9 2
= 73 T n/23 + n + · n + n
4 2 4 2 2
! ! 3
" . / " ! "2
n/2 9 n 2 7 9 2 7 9 2 9 2
= 73 7 T + 3
+ n + · n + n
2 2 2 4 2 4 2 2
! "3 ! "2
# $ 7 9 2 7 9 2 7 9 2 9 2
= 74 T n/24 + n + n + · n + n
4 2 4 2 4 2 2
...
! "k→1 ! "2 ! "1 ! "0
k
# k
$ 7 9 2 7 9 2 7 9 2 7 9 2
= 7 T n/2 + n + ... + n + n + n
4 2 4 2 4 2 4 2
k→1 ! "i
k
# k
$ 9 2' 7
= 7 T n/2 + n
2 i=0
4
# 7 $k
# $ 9 ↔1
= 7k T n/2k + n2 47
2 ↔1
! 4k "
k
# k
$ 2 7
= 7 T n/2 + 6n ↔1
4k
# $ 
# log (7) $k # $ log2 (7) k
k 2 2
= 2 2 T n/2 + 6n ↔1
(22 )k
 # $log (7) 
# k $log2 (7) # $ k 2
2
= 2 T n/2k + 6n2 ↔1
(2k )2
= 7nlog2 (7) ↔ 6n2
# $
= O nlog2 (7) ,

where log2 (7) ↖ 2.81 < 3! In this unfolding, we used the following trick: a = blogb (a) . When
you think about it... this is simply the definition of the logarithmic function...
There exist some faster algorithms to solve this problem. One that is well-known is due to
Coppersmith & Winograd (1990), which takes O (n2.38 ) time. However, the description of
this algorithm is so involved that it is not clear whether it can actually be implemented.

2.3.1 Master Theorem

Take a step back and look at all the examples of unfolding we have done so far in this chapter
(you can also refer to the examples of unfolding you did in CSI-2101). We always follow the

59
same logic. Why not do it once and for all? Let us say we have a general recurrence

T (n) = a · T (n/b) + nd

for some constants a ≃ 1, b > 1 and d ≃ 0. Let us try to unfold it (we assume n = bk and
T (1) = C ste for some integer k and some constant C ste ). We find

T (n) = a · T (n/b) + nd
! ! " . / "
n/b n d
=a a·T + + nd
b b
a
= a2 · T (n/b2 ) + d · nd + nd
! ! b"
n/b 2 . n /d " a
2
=a a·T + 2 + d · nd + nd
b b b
. a /2 a
= a3 · T (n/b3 ) + d nd + d · nd + nd
! ! b
" b
n/b 3 . n /d " . a /2 a
= a3 a · T + 3 + d nd + d · nd + nd
b b b b
. a /3 . a /2 a
= a4 · T (n/b4 ) + d nd + d nd + d · nd + nd
b b b
..
.
. a /k→1 . a /2 a
= ak · T (n/bk ) + d nd + ... + d nd + d · nd + nd
b b b
k→1 .
' /
a i
= ak · T (1) + nd
i=0
bd

and here we must be careful. The value of the sum depends on whether a < bd , a = bd or
a > bd . We skip the details, but if you do the math, you get the following theorem.
Theorem 2.1 (Master Theorem). Let T : N ↔→ R+ be a function. Suppose that for an
integer m ≃ 1, 
O(1) if n = m,
T (n) =
a · T (n/b) + O(n ) if n > m,
d

where a ≃ 1, b > 1 and d ≃ 0.

# $
• If d > logb (a), then T (n) = O nd .
# $
• If d = logb (a), then T (n) = O nd log(n) .
# $
• If d < logb (a), then T (n) = O nlogb (a) .

In the definition of T (n), one can think of m as the size of the input for the base case of
the recursion. The expression n/b corresponds to the size of the sub-problems and a is the

60
number of recursive calls. Finally, O(nd ) is the amount of work that is done outside of the
recursive calls.
Merge sort: T (n) = 2T (n/2) + O(n)
1D-Peak: T (n) = T (n/2) + O(1)
2D-Peak: T (n) = T (n/2) + O(n)
Strassen: T (n) = 7 T (n/2) + O(n2 )
Binary Search: T (n) = T (n/2) + O(1)

2.3.2 Selection Algorithm

In this section, we want to solve the following problem.

INPUT: A list S of n numbers and an integer k with 1 ⇐ k ⇐ n.

OUTPUT: The k-th smallest element in S.

Before we move any further, let us clarify what we mean by “k-th smallest element”. Given
a list S = ↙a1 , a2 , a3 , ..., an ∝, the k-th smallest element of S is the element we would find at
position k if the list was sorted. For instance, the 1-st smallest element of S is the minimum
element of S, and the n-th smallest element of S is the maximum element of S.
Consider the following list: ↙1, 4, 6, 0, 1, 1, 5∝. What is the 3-rd smallest element? Well, if the
list was sorted, then the list would be ↙0, 1, 1, 1, 4, 5, 6∝. And what is the element at position
3? It is 1. So the 3-rd smallest element of ↙1, 4, 6, 0, 1, 1, 5∝ is 1.
Let us consider the list ↙1, 4, 6, 0, 1, 1, 5∝ again. What is the 1-st smallest element? It is 0.
What is the 7-th smallest element? It is 6. And what is the 4-th smallest element? It is 1.
When k = ↗n/2↘, then the k-th smallest element is the median. This is why people sometimes
refer to this problem as Finding the Median.
The definition of the k-th smallest element seems to suggest that we sort the list and return
the element at position k. So we get the following algorithm for free!

Algorithm EasySelect(S, k)
Input: A list S of n numbers and an integer k with 1 ⇐ k ⇐ n.
Output: The k-th smallest element in S.
1: Sort S
2: return the element at position k

And what is the running time?

• Sorting using Merge Sort takes O(n log(n)) time.

61
 • The return step takes O(k) = O(n) time (don’t forget that we are working with a list).

• TOTAL: O(n log(n)) + O(n) = O(n log(n)) time.

And then, obviously, the next question is... can we do faster? In EasySelect, where is the
bottleneck? What is the most expensive step? Indeed, it is the sorting step. So can we solve
this problem without sorting? When you think about it, we do not need to know the rank of
all elements in the list, we only need to know the element at rank k. So why sort the whole
list?

And since we are in a chapter about divide-and-conquer, let us try to use this approach!

Algorithm Selection(S, k)
Input: A list S of n numbers and an integer k with 1 ⇐ k ⇐ n.
Output: The k-th smallest element of S.
1: if |S| = 1 then
2: return the only element in S
3: else
4: Choose an element p in S (call it the pivot)
5: Split S into S< , S= and S>
6: if k ⇐ |S< | then
7: Run Selection(S< , k)
8: else if k > |S< | + |S= | then
9: Run Selection(S> , k ↔ |S< | ↔ |S= |)
10: else
11: return p
12: end if
13: end if

On Line 4 of Selection, we choose an element p from S. The sets S< , S= and S> from Line 5
are defined as follows. The set S< contains all elements from S that are strictly smaller than
p, the set S= contains all occurrences of p in S, and the set S> contains all elements from S
that are strictly larger than p. We can then decide where to recurse depending on how big
k is compared to S< and S< ′ S= .

The running time of Selection(S, k) depends on the pivot p. In the worst case, here is what
can happen:

• all elements in S are di"erent,

• S is sorted,

• k = 1,

62
 • in each recursive call, p is chosen as the largest element6 .
Let us analyse the running time in such a situation. We can assume that choosing the pivot
(Line 4) takes O(1) time. If |S| = n, then splitting S into the three subsets (Line 5) takes
O(n) time. Observe that, since k = 1 and p is the largest element of the list, we have
S> = ↙ ∝, S= = ↙p∝ and S< = S \ S= . As such, we recurse on a list of size n ↔ 1. The total
running time then becomes

n + (n ↔ 1) + (n ↔ 2) + (n ↔ 3) + ... + 3 + 2 + 1 = O(n2 ).

A good case would be where, in each recursive call, p is chosen as the median. In this case,
the running time of Selection would satisfy

T (n) = T (n/2) + n.

Using the Master Theorem with a = 1, b = 2 and d = 1, we find T (n) = O(n), which would
be great! The problem is that we do not know how to find the median of S. This is precisely
the problem we are trying to solve (with k = ↗n/2↘)! So instead of finding the median itself,
let us try to figure out how to find a number that is “close” to the median.
One option would be to choose p randomly. Intuitively, on average, p will be close to the
median. In order to analyze the running time of this approach, you will need to study
randomized algorithms (and this semester, we only do deterministic).
How close to the median do we need p to be in order to get a linear-time algorithm? And
how can we find such a p e!ciently?
Here is what we mean by “close to the median” (From now on, to simplify the discussion, we
assume that all elements in S are di"erent).

Assume that there is a constant 0 < ε < 1 such that in Selection(S, p), it is always possible
to choose a pivot p satisfying |S< | ⇐ ε n and |S> | ⇐ ε n

If we can satisfy this assumption, then the running time of Selection becomes

T (n) = T (ε n) + n
= T (ε2 n) + ε n + n
= T (ε3 n) + ε2 n + ε n + n
..
.
n→1
'
= T (1) + n εi
i=0

6
We did not specify how to choose p. As such, depending on how the algorithm is implemented, we could
end up in a situation where p is chosen as the largest element at each recursive call.

63
 1 ↔ εn
=1+n
1↔ε
1
⇐1+n
1↔ε
= O(n).

Ok but how do we find such a pivot (and such an ε)?!

This is what Blum, Floyd, Pratt, Rivest and Tarjan discovered in 1973. Here is the trick.

Step 1 : Divide the input list into n

5
groups, each of size 5.

Step 2 : For i = 1, 2, ..., n/5, compute the median of the i-th group, call this median mi .

Step 3 : Compute the median p of m1 , m2 , ..., mn/5 .

We can now use the p from Step 3 in Selection(S, k). Let us see why p is a good pivot.
In other words, what value of ε do we get with this pivot? Let us start by estimating how
many numbers in S are larger than p.

Suppose we write the elements of S into columns of 5 elements. Each column corresponds
to one of the groups we created in Step 1. Suppose we sort each column from bottom to
top7 .

sorted
sorted

medians

n/5 n/5

Then where is the median of each group? In the middle row. Now suppose we sort the
columns with respect to their medians. The group of 5 with the smallest median then
corresponds to the leftmost column and the group of 5 with the largest median corresponds
to the rightmost column So where is p now? It appears in the middle row and the middle
column.
7
The algorithm is not sorting anything. This is part of our counting argument.

64
 sorted

sorted
p medians

n/10
n/5

What can we say about the elements in top right rectangle 10 n

⇓ 3? Each of these elements
is larger than or equal to the median of its group, but the medians of all these groups are
all at least as large as p. In other words, all the elements in this rectangle are larger than
or equal to p. So we found 10 n
⇓ 3 elements that are larger than or equal to p (there could
be even more). So we have |S> | ≃ 3n 10
, i.e., |S< | ⇐ 7n
10
. With a symmetric reasoning, we can
show that |S> | ⇐ 10 . So the constant ε we were looking for earlier is ε = 10
7n 7
.
Hence, with this choice of pivot, we have ε = 107
. Now that we have all the ingredients in
place, let us analyse the running time of Selection(S, k). Let T (n) denote the numbers of
steps taken by Selection(S, k) on a list S with n elements. We first compute p. How many
steps do we need for that?
Step 1 : Divide the input list into n
5
groups, each of size 5.
↔→ This step takes at most n steps. Indeed, you scan and you split!
Step 2 : For i = 1, 2, ..., n/5, compute the median of the i-th group, call this median mi .
↔→ For each group of 5 elements, we need to find its median. How do we do that? We
have only 5 elements, so we can simply sort them and return the third element.
This takes at most 5 log2 (5) + 3 ⇐ 18 steps using merge sort. Since we do that n5
times, this takes at most 18 n5 ⇐ 4n steps in total.
Step 3 : Compute the median p of m1 , m2 , ..., mn/5 .
↔→ How do we calculate the median of m1 , m2 , ..., mn/5 ? By calling Selection recur-
sively! More precisely, we call Selection(↙m1 , m2 , ..., mn/5 ∝, 10
n
). This takes T ( n5 )
time.
Once we have the pivot, it takes at most n steps to build S< , S= and S> . Then we make a
recursive call on a sub-problem of size at most 7n
10
. This takes T ( 7n
10
) time. In total, we find
T (n) ⇐ T (n/5) + T (7n/10) + 6n.
But how do we solve this recurrence? Unfolding gets (very) messy! The Master theorem
does not apply. What are our options, then?

65
We will prove, by induction on n, that T (n) = O(n).
Lemma 5. Let T (n) be a function such that

T (n) ⇐ T (n/5) + T (7n/10) + 6n. (2.4)

Then T (n) = O(n).

Proof. We will prove by induction on n that there exists a constant c for which T (n) ⇐ c · n.
The crux of the proof is that we do not know yet what c is. We will proceed with an inductive
argument which will tell us what c should be for the proof to work. We sometimes refer to
such a proof technique as constructive induction.
For the base case, observe that (2.4) only applies when n ≃ 5. So for the base case, assume
1 ⇐ n ⇐ 5. We do not know yet what c is, but we can take any constant c such that

T (1) ⇐ c · 1,
T (2) ⇐ c · 2,
T (3) ⇐ c · 3,
T (4) ⇐ c · 4,
T (5) ⇐ c · 5.

In other words, we can take any constant c such that

 
T (1) T (2) T (3) T (4) T (5)
c ≃ max , , , , .
1 2 3 4 5

For the induction hypothesis, suppose T (m) ⇐ c · m for all 1 ⇐ m < n.

Then, for the induction step, we have

T (n) ⇐ T (n/5) + T (7n/10) + 6n

n 7n
⇐c· +c· + 6n by the induction hypothesis,
5 10
9n
=c· + 6n.
10
Is it true that
9n
c· + 6n ⇐ c · n?
10
(If so, then we are done.) Is it true that
1
6n ⇐ c · n?
10
Is it true that
1
6⇐c· ?
10
66
Yes, provided that c ≃ 60.
When we put everything together, we obtain that the whole argument works as long as
 
T (1) T (2) T (3) T (4) T (5)
c ≃ max 60, , , , , .
1 2 3 4 5

This completes the proof.

67