Lower Bound on Comparision based Sorting
Prof. Prateek Vishnoi
August 21, 2024
Comparision based Sorting
Definition
Any sorting algorithm that determines the ordering of
elements only by comaring of two elements.
Prof. Prateek Vishnoi Lower Bound on Comparision based Sorting
Comparision based Sorting
Definition
Any sorting algorithm that determines the ordering of
elements only by comaring of two elements.
Merge Sort, Quick Sort, Insertion Sort are the examples.
Prof. Prateek Vishnoi Lower Bound on Comparision based Sorting
Claim
Theorem
Any deterministic comparision based algorithm must perform
Ω(n log n) comparisons to sort n elements in the worst case.
Proof
Prof. Prateek Vishnoi Lower Bound on Comparision based Sorting
Claim
Theorem
Any deterministic comparision based algorithm must perform
Ω(n log n) comparisons to sort n elements in the worst case.
Proof
Note : Any Sorting algorithm A must output a permutation
of the input I= [a1 , a2 . . . an ].
Prof. Prateek Vishnoi Lower Bound on Comparision based Sorting
Claim
Theorem
Any deterministic comparision based algorithm must perform
Ω(n log n) comparisons to sort n elements in the worst case.
Proof
Note : Any Sorting algorithm A must output a permutation
of the input I= [a1 , a2 . . . an ].
There are n! different possible permutations of the input.
Prof. Prateek Vishnoi Lower Bound on Comparision based Sorting
Claim
Theorem
Any deterministic comparision based algorithm must perform
Ω(n log n) comparisons to sort n elements in the worst case.
Proof
Note : Any Sorting algorithm A must output a permutation
of the input I= [a1 , a2 . . . an ].
There are n! different possible permutations of the input.
For ex: the permutation [a3 , a1 , a4 , a2 ] is correct for sorting
the input I = [2, 4, 1, 3].
Prof. Prateek Vishnoi Lower Bound on Comparision based Sorting
Claim
Theorem
Any deterministic comparision based algorithm must perform
Ω(n log n) comparisons to sort n elements in the worst case.
Proof
Note : Any Sorting algorithm A must output a permutation
of the input I= [a1 , a2 . . . an ].
There are n! different possible permutations of the input.
For ex: the permutation [a3 , a1 , a4 , a2 ] is correct for sorting
the input I = [2, 4, 1, 3].
For each permutation, there exist an input for which that
permutation is the correct answer.
Prof. Prateek Vishnoi Lower Bound on Comparision based Sorting
Continued...
Proof
Prof. Prateek Vishnoi Lower Bound on Comparision based Sorting
Continued...
Proof
WLOG lets assume the input is some permutation of
[1, 2, 3 . . . n]
Prof. Prateek Vishnoi Lower Bound on Comparision based Sorting
Continued...
Proof
WLOG lets assume the input is some permutation of
[1, 2, 3 . . . n]
Let S be the set of all inputs that are consistent with answers
to all comparisions made so far.
Prof. Prateek Vishnoi Lower Bound on Comparision based Sorting
Continued...
Proof
WLOG lets assume the input is some permutation of
[1, 2, 3 . . . n]
Let S be the set of all inputs that are consistent with answers
to all comparisions made so far.
Initially, |S| = n!(contains all permutations)
Prof. Prateek Vishnoi Lower Bound on Comparision based Sorting
Continued...
Proof
WLOG lets assume the input is some permutation of
[1, 2, 3 . . . n]
Let S be the set of all inputs that are consistent with answers
to all comparisions made so far.
Initially, |S| = n!(contains all permutations)
Each comparison divides the set S in two parts :
Prof. Prateek Vishnoi Lower Bound on Comparision based Sorting
Continued...
Proof
WLOG lets assume the input is some permutation of
[1, 2, 3 . . . n]
Let S be the set of all inputs that are consistent with answers
to all comparisions made so far.
Initially, |S| = n!(contains all permutations)
Each comparison divides the set S in two parts :
S ′ = All permutations that are consistent with the comparision
result.
Prof. Prateek Vishnoi Lower Bound on Comparision based Sorting
Continued...
Proof
WLOG lets assume the input is some permutation of
[1, 2, 3 . . . n]
Let S be the set of all inputs that are consistent with answers
to all comparisions made so far.
Initially, |S| = n!(contains all permutations)
Each comparison divides the set S in two parts :
S ′ = All permutations that are consistent with the comparision
result.
S ′′ = All permutations that are inconsistent with the
comparision result.
Prof. Prateek Vishnoi Lower Bound on Comparision based Sorting
Continued...
Proof
WLOG lets assume the input is some permutation of
[1, 2, 3 . . . n]
Let S be the set of all inputs that are consistent with answers
to all comparisions made so far.
Initially, |S| = n!(contains all permutations)
Each comparison divides the set S in two parts :
S ′ = All permutations that are consistent with the comparision
result.
S ′′ = All permutations that are inconsistent with the
comparision result.
At max. size of |S| reduces by factor of 2.
Prof. Prateek Vishnoi Lower Bound on Comparision based Sorting
Continued...
Proof
WLOG lets assume the input is some permutation of
[1, 2, 3 . . . n]
Let S be the set of all inputs that are consistent with answers
to all comparisions made so far.
Initially, |S| = n!(contains all permutations)
Each comparison divides the set S in two parts :
S ′ = All permutations that are consistent with the comparision
result.
S ′′ = All permutations that are inconsistent with the
comparision result.
At max. size of |S| reduces by factor of 2.
At the end, algorithm must have |S| = 1 in order to know
which output is correct.
Prof. Prateek Vishnoi Lower Bound on Comparision based Sorting
Continued...
S n!
1 comparision
S n!/2
1 comparision
n!/4
S
1 comparision
S 1
Prof. Prateek Vishnoi Lower Bound on Comparision based Sorting
Continued...
Prof. Prateek Vishnoi Lower Bound on Comparision based Sorting
Continued...
Least number of comparisions = log(n!)
Prof. Prateek Vishnoi Lower Bound on Comparision based Sorting
Continued...
Least number of comparisions = log(n!)
Hope that you remember how to solve it.
Prof. Prateek Vishnoi Lower Bound on Comparision based Sorting
Continued...
Least number of comparisions = log(n!)
Hope that you remember how to solve it.
Total number of comparisons = Ω(n log n)
Prof. Prateek Vishnoi Lower Bound on Comparision based Sorting
Claim
Theorem
Any deterministic comparision based algorithm must perform
Ω(n log n) comparisons to sort n elements in the average case.
Proof.
Prof. Prateek Vishnoi Lower Bound on Comparision based Sorting
Claim
Theorem
Any deterministic comparision based algorithm must perform
Ω(n log n) comparisons to sort n elements in the average case.
Proof.
We need to show that out of all binary trees on a given no. of
leaves, one that minimises the average depth is completely
balanced binary tree.
Prof. Prateek Vishnoi Lower Bound on Comparision based Sorting
Claim
Theorem
Any deterministic comparision based algorithm must perform
Ω(n log n) comparisons to sort n elements in the average case.
Proof.
We need to show that out of all binary trees on a given no. of
leaves, one that minimises the average depth is completely
balanced binary tree.
Assume that one unbalanced binary tree minimises the
average depth.[Difference of largest and smallest depth is ≥ 2]
Prof. Prateek Vishnoi Lower Bound on Comparision based Sorting
Claim
Theorem
Any deterministic comparision based algorithm must perform
Ω(n log n) comparisons to sort n elements in the average case.
Proof.
We need to show that out of all binary trees on a given no. of
leaves, one that minimises the average depth is completely
balanced binary tree.
Assume that one unbalanced binary tree minimises the
average depth.[Difference of largest and smallest depth is ≥ 2]
Let d and D be the smallest and largest depth of tree.
Prof. Prateek Vishnoi Lower Bound on Comparision based Sorting
Claim
Theorem
Any deterministic comparision based algorithm must perform
Ω(n log n) comparisons to sort n elements in the average case.
Proof.
We need to show that out of all binary trees on a given no. of
leaves, one that minimises the average depth is completely
balanced binary tree.
Assume that one unbalanced binary tree minimises the
average depth.[Difference of largest and smallest depth is ≥ 2]
Let d and D be the smallest and largest depth of tree.
Take 2 siblings at larger depth and move to the children of
the leaf of smallest depth.
Prof. Prateek Vishnoi Lower Bound on Comparision based Sorting
Claim
Theorem
Any deterministic comparision based algorithm must perform
Ω(n log n) comparisons to sort n elements in the average case.
Proof.
We need to show that out of all binary trees on a given no. of
leaves, one that minimises the average depth is completely
balanced binary tree.
Assume that one unbalanced binary tree minimises the
average depth.[Difference of largest and smallest depth is ≥ 2]
Let d and D be the smallest and largest depth of tree.
Take 2 siblings at larger depth and move to the children of
the leaf of smallest depth.
Above operation removes two leaves of depth D and 1 leaf of
depth d and introduces 2 leaves of depth d + 1 and one of
depth (D − 1)
Prof. Prateek Vishnoi Lower Bound on Comparision based Sorting
Claim
Theorem
Previous bounds also holds for randomised algorithms.
Proof.
Prof. Prateek Vishnoi Lower Bound on Comparision based Sorting
Claim
Theorem
Previous bounds also holds for randomised algorithms.
Proof.
Think of randomised algorithm as a probability distribution
over the deterministic algorithms.
Prof. Prateek Vishnoi Lower Bound on Comparision based Sorting
Claim
Theorem
Previous bounds also holds for randomised algorithms.
Proof.
Think of randomised algorithm as a probability distribution
over the deterministic algorithms.
Since probability distribution is uniform distribution and for
any deterministic algorithm we have proved the bound of
Ω(n log n)
Prof. Prateek Vishnoi Lower Bound on Comparision based Sorting
Claim
Theorem
Previous bounds also holds for randomised algorithms.
Proof.
Think of randomised algorithm as a probability distribution
over the deterministic algorithms.
Since probability distribution is uniform distribution and for
any deterministic algorithm we have proved the bound of
Ω(n log n)
This argument suffices the proof.
Prof. Prateek Vishnoi Lower Bound on Comparision based Sorting