Register

Cormen Edition 3 Exercise 9.1 Question 2 (Page No. 215)

1,905 views
0 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

Voting & Accepting an answer helps improve the community
← Previous · Cormen Edition 3 Exe...Next → · Cormen Edition 3 Exe...
← Previous in category · Cormen Edition 3 Exe...Next in category → · Cormen Edition 3 Exe...
Position:
Show:

Related questions

0 0 votes
2 2 answers
845
845 views
akash.dinkar12 asked Jun 28, 2019
845 views
Cormen Edition 3 Exercise 9.1 Question 1 (Page No. 215)
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 0 votes
0 0 answers
472
472 views
akash.dinkar12 asked Jun 27, 2019
472 views
Cormen Edition 3 Exercise 6.5 Question 9 (Page No. 166)
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 0 votes
0 0 answers
382
382 views
akash.dinkar12 asked Apr 5, 2019
382 views
Cormen Edition 3 Exercise 4.4 Question 9 (Page No. 93)
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 0 votes
1 1 answer
1.3k
1.3k views
akash.dinkar12 asked Apr 5, 2019
1,269 views
Cormen Edition 3 Exercise 4.3 Question 9 (Page No. 88)
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...