Consider the following algorithm for finding a target element t in an array x_1,

Question

Consider the following algorithm for finding a target element t in an array x_1, x_2, ..., x_n. Assume as a precondition that exactly one of the x'_i s is equal to t. choose i at random from {1, 2, ..., n}. while x_i notequalto t do choose i at random from {1, 2 ..., n). print Element t was found in location i. This algorithm continues to guess randomly until it finds where t is. Note that it does not keep track of its previous guesses, so it may check the same location more than once. (a) Find the best-case number of notequalto comparisons made by this algorithm. (b) Warning: Tricky. Find the worst-case number of notequalto comparisons made by this algorithm. (c) Calculus required. Use the sum of an infinite series to find the averagecase number of notequalto comparisons made by this algorithm.

Explanation / Answer

a.) The best case number of comparison made by this algo. is 1 as it may be the case that given algo. finds the number at first guess.

b.) For the worst case, it might be possible that algo. keep running forever until it is halted by the user or system. So, we don't have exact numerical value for it.

c.) An element can be found in 1, 2, 3,.., inf iterations. Therefore average case will be

(1 + 2 + 3 + ...+ inf)/n = inf

Hope it helps, feel free to comment in case of any query.

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

---

---

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