A: Describe an algorithm that, upon input of n real numbers denoted a(1),a(2),a(

Question

A: Describe an algorithm that, upon input of n real numbers denoted a(1),a(2),a(3)...,a(n) and another number x, determine which numbers in the list sre stricly greater than x.
B: Find the complexity function of the algorithm.

Explanation / Answer

Since there are no constraints suggested such as space and running time we can give an algorithm as Input : n real numbers and x Output : numbers greater than x Procedure: 1) Mantain an empty list L. 2) Scan all the numbers one by one . 3) If number > x add it to L Complexity : Above algo will take O(n) as it involves just a left to right scan of a(1) .... a(n) Also note that we can say that we need minimum of n-1 comparisons as if we associate a boolean variable for each number in array a then if we someone provides an algorithm with n-2 steps we can say that there must be a number with boolean variable = False and thus has not been checked by our algorithm.

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

---

---

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