Describe an algorithm that, upon input of n real numbers denoted a1; a2; a3 : :

Question

Describe an algorithm that, upon input of n real numbers denoted a1; a2; a3 : : : ; an and another number x, determines which numbers in the list are stricly greater than x.

Explanation / Answer

list : a1,a2,a3,a4,a5 .... an elm_to_compare with : x since we need to find elements greater than x . We have 2 approaches : a. Sort the list in descending order and keep track of sentinel which is .. ai >= x where is max value satisfying the condition . Once the list is sorted you can retrieve the elements greater than sentinel in constant time O(1) . so total complexity is : complexity for sort [ merge/heap] + retrieve step O(nlogn) + O(1) b. Compare each element ai with x . Push ai into another list if ai > x . this is repeated for n times ie for a1... an . Hence the complexity is O(n) . The time to push greater element to another list is constant O(1).

Related Questions

Navigate

• Browse (All)
• Browse D
• Subjects

---

---

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