I claim that merge-sort is actually a linear time algorithm -- i.e., faster than (NlogN).

Below is a sketch of my proof that the runtime of merge-sort is actually .

For simplicity, I am only proving my claim for powers of 2 (so I don't have to worry about floors and ceilings).

We already know that the runtime of merge-sort is described by the recurrence relation

for

I want to show that . To make this Big-Oh claim, I will show that that for all and some constant .

BASE-CASE: as long as clearly such a constant exists!

INDUCTIVE HYPOTHESIS: Assume the claim holds for powers of 2 less than where is itself a power of 2:

where (and so ).

Notice that this covers

Now I have to prove the claim holds at .

PROOF:

from recurrence relation and

by I.H. applied to

algebra

algebra

because is a constant and

a constant times is still ,

since we know that "constants don't matter"!

Q.E.D.

Of course, I am wrong! The runtime of MergeSort is really .

Your Job: Answer this question:

What is fundamentally wrong with my proof?