LOWER BOUND: Your friend John claims to have a comparison based data structure,

Question

LOWER BOUND: Your friend John claims to have a comparison based data structure, which can support two methods: insert and extract_almost_min. Here the extract_almost_min operations returns either the minimum item in the structure or second minimum and doesn't tell you which item it returned. He further claims that both this operations can be done in O(1) time. Prove that his claim is wrong! (Hint: If his claim was right, show how you can use this to sort n numbers in O(n) time contradicting the sorting lower bound).

Explanation / Answer

If the claim is true, we could use it sort n numbers in O(n) 1. insert n numbers in the data structure n x O(1) 2. x = extract_almost_min O(1) 3. y = extract_almost_min O(1) 4. compare x and y, put in the result list (sorting order) accordingly O(1), comparing two numbers require constant time 5. repeat steps 2-4 until the data structure becomes empty 6. return result list We know that, the minimum time for sorting is O(nlgn), so the claim is WRONG!

Related Questions

Navigate

• Browse (All)
• Browse L
• Subjects

---

---

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