452 views

2 Answers

0 votes
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
0 votes
1 answer
1
0 votes
0 votes
0 answers
2
akash.dinkar12 asked Jun 27, 2019
305 views
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 minhea...
0 votes
0 votes
0 answers
3
akash.dinkar12 asked Apr 5, 2019
182 views
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...
0 votes
0 votes
1 answer
4
akash.dinkar12 asked Apr 5, 2019
898 views
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 integr...