Derivation of the
Sorting Lower-Bound
Sorting Lower-Bound
lA
sorting algorithm effectively establishes which of n! permutations the data are originally in and
through a series of comparisons and exchanges permutes the data to a fixed
order.
lThis can be viewed as a tree with n! nodes, constructed with binary internal nodes for comparisons.
lThis can be viewed as a tree with n! nodes, constructed with binary internal nodes for comparisons.