Data Structures and Algorithms
Dr. N. L. Bhanu Murthy
BITS Pilani Computer Science & Information Systems Department
Pilani Campus
Lower Bound on Sorting Algorithms (comp based)
What is the best we can do on comparison based sorting?
Best worst-case sorting algorithm (so far) is O(N log N)
Can we do better (or) Can we prove a lower bound on the
sorting problem, independent of the algorithm?
For comparison sorting, we can show lower bound of Ω(N log N)
BITS Pilani, Pilani Campus
Decision Tree for Sorting Algorithms
A decision tree is a binary tree where:
– Each node
• lists all left-out open possibilities (for deciding)
– Path of each node
• represents a decided sorted prefix of elements
– Each branch
• represents an outcome of a particular comparison
– Each leaf
• represents a particular ordering of the original array elements
BITS Pilani, Pilani Campus
Root = all open
possibilities IF a<b:
possible
A decision tree to sort
three elements {a,b,c}
(assuming no
duplicates)
Height =
all remaining (lg n!)
open
possibilities IF a<c:
possible
Worst-case n! leaves
evaluation path in this tree
for any algorithm 4 4
BITS Pilani, Pilani Campus
Decision-tree example
Sort a1, a2, …, an 1:2
2:3 1:3
123 1:3 213 2:3
132 312 231 321
Each internal node is labeled i:j for i, j {1, 2,…, n}.
• The left subtree shows subsequent comparisons if ai aj.
• The right subtree shows subsequent comparisons if ai aj.
BITS Pilani, Pilani Campus
Decision-tree example
Sort a1, a2, a3 9, 4, 6
1:2 94
2:3 1:3
123 1:3 213 2:3
132 312 231 321
Each internal node is labeled i:j for i, j {1, 2,…, n}.
• The left subtree shows subsequent comparisons if ai aj.
• The right subtree shows subsequent comparisons if ai aj.
BITS Pilani, Pilani Campus
Decision-tree example
Sort a1, a2, a3 9, 4, 6
1:2
2:3 1:3 96
123 1:3 213 2:3
132 312 231 321
Each internal node is labeled i:j for i, j {1, 2,…, n}.
• The left subtree shows subsequent comparisons if ai aj.
• The right subtree shows subsequent comparisons if ai aj.
BITS Pilani, Pilani Campus
Decision-tree example
Sort a1, a2, a3 9, 4, 6 1:2
2:3 1:3
123 1:3 213
4 6 2:3
132 312 231 321
Each internal node is labeled i:j for i, j {1, 2,…, n}.
• The left subtree shows subsequent comparisons if ai aj.
• The right subtree shows subsequent comparisons if ai aj.
BITS Pilani, Pilani Campus
Decision-tree example
Sort a1, a2, a3 9, 4, 6
1:2
2:3 1:3
123 1:3 213 2:3
132 312 231 321
469
Each leaf contains a permutation , ,…, (n) to
indicate that the ordering a(1) a(2) a(n) has been
established.
BITS Pilani, Pilani Campus
Decision Tree for Sorting Algorithms
The logic of any sorting algorithm that uses comparisons can be
represented by a decision tree
In the worst case, the number of comparisons used by the
algorithm equals the HEIGHT OF THE DECISION TREE
In the average case, the number of comparisons is the average
of the depths of all leaves
There are N! different orderings of N elements
BITS Pilani, Pilani Campus
Lower bound for decision-tree sorting
Theorem. Any decision tree that can sort n elements must
have height (n lg n) .
Proof. The tree must contain n! leaves, since there are n!
possible permutations.
A height-h binary tree has 2h leaves.
Thus, n! 2h .
h lg(n!) (lg is mono. increasing)
lg ((n/e)n) (Stirling’s formula)
= n lg n – n lg e
= (n lg n) .
since n lg n – n lg e n lg n for all n >= n0 (take n0 to be
100) BITS Pilani, Pilani Campus
Problem Complexity
if
if
BITS Pilani, Pilani Campus
Optimal Algorithm
Corollary. Merge sort and Heap Sort are asymptotically
optimal comparison sorting algorithms.
BITS Pilani, Pilani Campus
BITS Pilani, Pilani Campus
Comparing P and Q
BITS Pilani, Pilani Campus
Comparing P and Q
BITS Pilani, Pilani Campus
Thank You!!
BITS Pilani, Pilani Campus
