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.)

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

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