1,207 views
0 votes
0 votes
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.)

1 Answer

Related questions

0 votes
0 votes
2 answers
1
akash.dinkar12 asked Jun 28, 2019
452 views
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
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...