March 19, 2011.
How many minimum comparisons are needed to trace second smallest element in an unsorted array?
We can use a tournament tree approach based on adversary argument to prove minimum number of comparisons.
In tournament method, every number (element) is paired with other number successively to find the maximum number. This forms a tree like structure. We must have N - 1 comparisons to find maximum number.
The information gained while finding max number will be used in reducing the comparisons for second largest. It meas, we would need to consider only those which lost against max number to be considered for second largest.
From the tree structure, we can conclude such lost numbers can't be more than [log(N) - 1] (consider tree height).
Overall, at minimum we need ( N - 1 + log(N) - 1 = N + log(N) - 2 ) comparisons.
Read my post on Geeksforgeeks for details on Winner tree approach.
No comments:
Post a Comment