[Oops.] Off-by-one errors in Lemma 1.1 proof

[emilykfox]

Please verify that the error is present in the most recent revision before reporting. Downloaded today.

Chapter number or note title: Chapter 1: Recursion

Page number: 28

Error description:

1. In the first paragraph of Lemma 1.1's proof, you make a claim about all k from 0 to n. However, B[0 .. n] is not well-defined, and you miss the base case of k > n that you discuss in the next paragraph.

2. The claim mentioned above discusses the last n - k - 1 iterations of the for loop, but there are n - k + 1 iterations remaining when iteration k begins.

Suggested fix (if any):

1. Change "0 to n" to "1 to n + 1".

2. Change "n - k - 1" to "n - k + 1".

[emilykfox]

An alternative idea for this section: you could describe merge as identifying the last element of the output array and recursively merging the rest of the input arrays. Then the for loop would go k <- n to 1.

Doing so means you can do induction on k instead of n - k + 1, so it might be easier to follow. The first error makes me think you may have written Merge this way originally.

On the other hand, now you'd be the one person [citation needed] whose merge runs backwards compared to everybody else.