Algorithms Consider the problem of finding the median of a three-element set {a,

Question

Algorithms

Consider the problem of finding the median of a three-element set {a, b, c} of items that can be ordered. What is the information-theoretic lower bound for comparison-based algorithms solving this prob­lem? How many outcomes does the problem have? Draw a decision tree for an algorithm solving this problem. Of course, there are many ways to solve this simple problem. If the worst-case number of comparisons in your algorithm is greater than the information-theoretic lower bound, do you think an algorithm matching the lower bound exists? (Either find such an algorithm or prove its impossibility.) Thinking about a, b, and c as points on the real line may help. (In any case, you need to justify your answer.)

Explanation / Answer

1) (log2(leaves)) = (log2(6))

the lower- bound is 2 comparisions - CAB or CBA

2)

3) quicksort can sort the elements in O(n log n) time.

there are 3 elements; O(3 log 3) = 1.43 =2

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.