CScD-320 Recurrence Example:
MergeSort / Optimal QuickSort Recurrence
This is available as a Word .doc file that prints in one page.

Let n be defined as 2^k for some k > 0.

For n = 1 (2⁰), there is no expense — the array is necessarily in order.

For n > 1, there is an expense of n (the merge step in one case, the partition step in the other), plus the expense of two recursive calls of the sorting algorithm for the size n/2.

As a recurrence, this becomes the following:

Propose (as supported by the table): f(n) = n * log₂(n) for n = 2^k for k > 0

f(1) = 0 [recurrence]
f(1) = 1 * lg(1) = 0 [formula]

Assume validity for f(n/2), prove for f(n)

f(n)	= n + 2 * f(n/2)	Recurrence
	= n + 2 * (n/2 * log2(n/2))	Inductive hypothesis
	= n + n * ( log2(n) – log2(2) )	Simplify; expand log2(n/2)
	= n + n * ( log2(n) – 1 )	Definition of log2(2)
	= n log2(n)	Simplify