What's wrong with this inductive proof that mergesort is O(n)?

Question

Comparison based sorting is big omega of nlog(n), so we know that mergesort can't be O(n). Nevertheless, I can't find the problem with the following proof:

Proposition P(n): For a list of length n, mergesort takes O(n) time.

P(0): merge sort on the empty list just returns the empty list.

Strong induction: Assume P(1), ..., P(n-1) and try to prove P(n). We know that at each step in a recursive mergesort, two approximately "half-lists" are mergesorted and then "zipped up". The mergesorting of each half list takes, by induction, O(n/2) time. The zipping up takes O(n) time. So the algorithm has a recurrence relation of M(n) = 2M(n/2) + O(n) which is 2O(n/2) + O(n) which is O(n).

Answer 1

Compare the "proof" that linear search is O(1).

1. Linear search on an empty array is O(1).
2. Linear search on a nonempty array compares the first element (O(1)) and then searches the rest of the array (O(1)). O(1) + O(1) = O(1).

The problem here is that, for the induction to work, there must be one big-O constant that works both for the hypothesis and the conclusion. That's impossible here and impossible for your proof.

Answer 2

The "proof" only covers a single pass, it doesn't cover the log n number of passes.

The recurrence only shows the cost of a pass as compared to the cost of the previous pass. To be correct, the recurrence relation should have the cumulative cost rather than the incremental cost.

You can see where the proof falls down by viewing the sample merge sort at http://en.wikipedia.org/wiki/Merge_sort

Answer 3

Here is the crux: all induction steps which refer to particular values of n must refer to a particular function T(n), not to O() notation!

O(M(n)) notation is a statement about the behavior of the whole function from problem size to performance guarantee (asymptotically, as n increases without limit). The goal of your induction is to determine a performance bound T(n), which can then be simplified (by dropping constant and lower-order factors) to O(M(n)).

In particular, one problem with your proof is that you can't get from your statement purely about O() back to a statement about T(n) for a given n. O() notation allows you to ignore a constant factor for an entire function; it doesn't allow you to ignore a constant factor over and over again while constructing the same function recursively...

You can still use O() notation to simplify your proof, by demonstrating:

T(n) = F(n) + O(something less significant than F(n))

and propagating this predicate in the usual inductive way. But you need to preserve the constant factor of F(): this constant factor has direct bearing on the solution of your divide-and-conquer recurrence!