Log In
0 votes
Show that the second smallest of $n$ elements can be found with $n+\lceil lg\ n \rceil -2$ comparisons in the worst case. (Hint: Also find the smallest element.)
in Algorithms 89 views

2 Answers

0 votes

this might help

0 votes
Assuming n is the power of 2 without loss of generality.Now we will perform the tournament search and form the tournament tree by comparing a pair of elements at a time.This will take total (n-1) comparisons to find the smallest element.This tournament tree will look like a complete binary tree but it will be in reverse orientation compared to the normal complete binary tree.Now start from the root.This will the smallest element.This we have obtained by comparing the two elements just before the previous level.Now one of the element will be smallest element itself.So leave this element.And take the other element.Now take a list and append the element into the list.Now take the branch where the smallest element is present.And then consider the two children.One will the smallest element itself and another will be the other element.So take that element and append it to the list.So If we continue in this way then the resulting list will contain ceil(logn) elements or the number of elements equal to the number of levels in the tree.This list will contain all the elements which are the potential candidates to become a second smallest element.Now to determine the second smallest element in the list we need ceil(logn)-1 comparisons.

So total number of comparisons wiil be =(n-1)+ceil(log)-1=n+ceil(logn)-2

Related questions

0 votes
1 answer
Prove the lower bound of $\lceil 3n/2\rceil – 2$ comparisons in the worst case to find both the maximum and minimum of $n$ numbers. (Hint: Consider how many numbers are potentially either the maximum or minimum and investigate how a comparison affects these counts.)
asked Jun 28, 2019 in Algorithms akash.dinkar12 64 views
0 votes
0 answers
Give an $O(n\lg\ k)$- time algorithm to merge $k$ sorted lists into one sorted list, where $n$ is the total number of elements in all the input lists. (Hint: Use a minheap for $k$-way merging.)
asked Jun 27, 2019 in Algorithms akash.dinkar12 68 views
0 votes
0 answers
Use a recursion tree to give an asymptotically tight solution to the recurrence $T(n)=T(\alpha n) +T((1-\alpha)n) +cn$,where $\alpha$ is a constant in the range $0<\alpha<1$ and $c>0$ is also constant.
asked Apr 5, 2019 in Algorithms akash.dinkar12 36 views
0 votes
1 answer
Solve the recurrence $T(n)=3T(\sqrt n) +log\ n$ by making a change of variables.Your solution should be asymptotically tight. Do not worry about whether values are integral.
asked Apr 5, 2019 in Algorithms akash.dinkar12 99 views