[go: up one dir, main page]
Scribd
Upload
86 views1 page

Sortcomplexity PDF

The document discusses the decision tree model for comparison-based sorting algorithms. It shows a decision tree for sorting a 3-element list with possible orderings as leaves. For a list with n elements, there must be n! leaves to represent all permutations. The number of leaves is upper bounded by 2 to the power of the tree height. Equating the number of leaves to n! and using Stirling's formula shows the lower bound of comparisons is Θ(n lg n).

Uploaded by

Andrew Lee
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
86 views1 page

Sortcomplexity PDF

The document discusses the decision tree model for comparison-based sorting algorithms. It shows a decision tree for sorting a 3-element list with possible orderings as leaves. For a list with n elements, there must be n! leaves to represent all permutations. The number of leaves is upper bounded by 2 to the power of the tree height. Equating the number of leaves to n! and using Stirling's formula shows the lower bound of comparisons is Θ(n lg n).

Uploaded by

Andrew Lee
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 1

Sorting Complexity

Every comparison-based sort has a corresponding decision tree. Consider


the following decision tree for an arbitrary sorting algorithm to sort a 3element list [A, B, C].
A:B

A:C

B:C

[ABC]

A:C

[CAB]

[BAC]

[ACB]

B:C

[BCA]

[CBA]

At every point in the tree, a comparison-based sort by definition will compare


2 elements. The leaves in the tree are all possible orderings for the list. For
a decision tree to represent all permutations of the array, there need to be
n! number of leaves. For a binary decision tree there is an upper bound on
the number of leaves possible:
L 2H

(1)

Substituting L = n! into the above inequality and using Stirlings Formula to expand the factorial gives
H n lg n + O(n)

(2)

Because the height of the tree is the number of comparisons done, the
optimal (lower-bound) number of comparisons for a comparison-based sort
is (n lg n).

You might also like