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

Question

Comparison sorting is a big omega nlog (n) , so we know that mergesort cannot be O (n) . However, I cannot find a problem with the following proof:

Sentence P (n) : for a list of length n , mergesort takes O (n) time.

P (0) : Merge sort on an empty list returns an empty list.

Strong induction: suppose P (1), ..., P (n-1) and try to prove P (n) . We know that at each stage of a recursive merge, two approximately “half-lists” are combined and then “fastened”. The merger of each semigroup by induction takes O (n / 2) time . Binding takes O (n) . Thus, the algorithm has a recurrence relation M (n) = 2M (n / 2) + O (n) , which is 2O (n / 2) + O (n) , which is O (n) .

Answer 1

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

• Linear search on an empty array - O (1).
• A linear search on a non-empty array compares the first element (O (1)), and then searches for the rest of the array (O (1)). O (1) + O (1) = O (1).

The problem is that for induction to work, there must be one constant of large O, working both for the hypothesis and for the conclusion. This is impossible and impossible for your proof.

Answer 2

"Proof" covers only one pass, it does not cover the logarithmic number of passes.

Repetition shows only the cost of the passage compared to the cost of the previous passage. To be true, the repetition ratio must have a total value, not a value increase.

You can see where the proof falls by looking at the sorting of the sample sample at http://en.wikipedia.org/wiki/Merge_sort

Answer 3

Here's the bottom line: all induction steps that relate to specific values ​​of n should relate to a specific function T (n), not O () notations!

The O (M (n)) notation is a statement about the behavior of the entire function from the size of the task to the guarantee of performance (asymptotically, since n increases unboundedly). The goal of your induction is to determine the performance-related T (n), which can then be simplified (by dropping constants and lower order coefficients) to O (M (n)).

In particular, one problem with your proof is that you cannot get from your statement purely about O () the statement about T (n) for a given n. O () allows you to ignore a constant coefficient for an entire function; this does not allow you to ignore the constant factor again and again when building the same function recursively ...

You can use the 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 keep a constant factor F (): this constant factor is directly related to solving your gap between shoots!