Prev: Invariants and Recursive Algorithms

What Every CMPT 225 Student Should Know About Mathematical Induction

- by Brad Bart, Simon Fraser University

Part 1: Overview of Induction

• Summary
• The Inductive Step
• The Basis Cases

Part 2: How Induction Relates to Computer Science

• Programming Using Induction
• Loop Invariants
• Invariants and Recursive Algorithms
• Running Time Analysis of Merge Sort

Part 2: How Induction Relates to Computer Science

Running Time Analysis of Merge Sort

Welcome keener, for a little bit of bonus math. Your objective? Given the recursive definition of T(n):

	T(n) =	{	O(1)  if n ≤ 1
			O(1) + T(⎡n/2⎤) + T(⎣n/2⎦) + O(n)  if n > 1

. . . show that T(n) = O(n log n), i.e., for constants c, n₀, the inequality T(n) ≤ c⋅n log n holds for every n ≥ n₀.

Preliminary Work

The first step is to rewrite the recurrence so that you're dealing with pure algebra, rather than the big-O, i.e., substitute O(n) ≤ an.

	T(n) ≤	{	O(1)  if n ≤ 1
			T(⎡n/2⎤) + T(⎣n/2⎦) + an  if n > 1

Second, note that the ceiling and floor operators are going to make life difficult for you. Certainly, when n is even, they have no effect, but when n is odd, they will add ± 1/2 to the result. This will mean two cases in the inductive step.

Inductive Step

Assume T(n) ≤ c⋅n log n holds for every n < k, and prove T(k) ≤ c⋅k log k.

Case 1: k is even

T(k)

≤ T(⎡k/2⎤) + T(⎣k/2⎦) + ak = T(k/2) + T(k/2) + ak ≤ c⋅(k/2) log(k/2) + c⋅(k/2) log(k/2) + ak                                       (Inductive Hypothesis) = c⋅k log(k/2) + ak = c⋅k (log k − log 2) + ak = c⋅k log k − ck log 2 + ak ≤ c⋅k log k                     (when c ≥ a / log 2)

Case 2: k is odd

T(k)

≤ T(⎡k/2⎤) + T(⎣k/2⎦) + ak = T((k + 1)/2) + T((k − 1)/2) + ak ≤ c⋅(k + 1)/2 log((k + 1)/2) + c⋅(k − 1)/2 log((k − 1)/2) + ak                                       (Inductive Hypothesis) = (c/2)⋅[(k + 1) log(k + 1) + (k − 1) log(k − 1)] − ck log 2 + ak

If you're still paying attention, you'll notice the symmetry with Case 1. Except for the first term, the two expressions are identical, and so if only you could show

(k + 1) log(k + 1) + (k − 1) log(k − 1) ≤ 2k log k,

you would be home. Unfortunately, this inequality is false, and you can prove it is false by using calculus, or perhaps even mathematical induction. But it turns out that the left hand side is not that much bigger than the right hand side, which means that you can utilize a portion of the − ck log 2 term to reduce its value by just enough to satisfy the inequality.

Back to the action:

T(k)

≤ (c/2)⋅[(k + 1) log(k + 1) + (k − 1) log(k − 1)] − ck log 2 + ak ≤ (c/2)⋅[(k + 1) log(k + 1) + (k − 1) log(k + 1)] − ck log 2 + ak = c⋅k log(k + 1) − ck log 2 + ak = c⋅k log(k + 1) − ck log 4/3 − ck log 3/2 + ak = c⋅k[log(k + 1) − log 4/3] − ck log 3/2 + ak = c⋅k log 3(k + 1)/4 − ck log 3/2 + ak ≤ c⋅k log k − ck log 3/2 + ak      (when 3(k + 1)/4 ≤ k, i.e., k ≥ 3) ≤ c⋅k log k                                  (when c ≥ a / log(3/2))

So, no matter whether k is even or odd, T(k) ≤ c⋅k log k, whenever k ≥ 3 and c ≥ max(a / log 2, a / log(3/2)) = a / log(3/2).

[You're almost there. There's one last detail to take care of.]

Basis Cases

The inductive step operates as long as the two subcases, i.e., T(⎡k/2⎤) and T(⎣k/2⎦), satisfy the inequality in the Inductive Hypothesis. Sadly, when k = 3, one of these subcases is T(1), which never satisfies T(n) ≤ c⋅n log n, no matter how large you pick your c.

The solution is to pick a larger k for the inductive step, say k ≥ 4. Finally, choose c so that it satisfies both T(2) ≤ c⋅2 log 2 and T(3) ≤ c⋅3 log 3. That is, c ≥ max(a / log(3/2), T(2) / (2 log 2), T(3) / (3 log 3)). □

       Elementary Data Structures