Derivation of the
Sorting Lower-Bound
Sorting Lower-Bound
lThe
worst-case run time of the sorting algorithm is the height of a tree having has n! nodes.
lThe minimum height of such a tree is log2(n!).
lBy StirlingŐs formula, n! ~ (2 p n)1/2 (n/e) n,
so
log2(n!) is O(n log(n)).
lThe minimum height of such a tree is log2(n!).
lBy StirlingŐs formula, n! ~ (2 p n)1/2 (n/e) n,
so
log2(n!) is O(n log(n)).