Java 6 Illuminated: An Active Learning Approach, 2nd Edition

1132 CHAPTER 15 Running Time Analysis

Proof by Induction Method

If we can guess the value of T1(n) as a function of n, then we can use a

proof by induction in order to prove that our guess is correct. We can use

the preceding iteration method to come up with a guess for T1(n).

Generally, a proof by induction works as follows:

■

Verify that our statement (equation in this case) is true for a base case.

■

Assume that out statement is true up to n.

■

Prove that it is true for n + 1.

Let’s go through the induction steps with our guess that T1(n) = 2 * n + 1,

which we may have generated from our iterative or handwaving method.

Step 1: Verify that the value that ...