Recall that for integers a_1, ..., a_n and an integer x, LinearSearch(x, a_1, ..
ID: 3820691 • Letter: R
Question
Recall that for integers a_1, ..., a_n and an integer x, LinearSearch(x, a_1, ..., a_n) returns the index of x if x is one of the elements of the list a_1, ..., a_n or returns 0 if x is not part of the list. LinearSearch has a runtime of Theta (1) in the best case, and Theta (n) in the worst case. Recall that for a sorted list of integers a_1, ..., a_n and an integer x, BinarySearch(x, a_1, ..., a_n) also returns the index of x if x is one of the elements of the list or returns 0 if x is not part of the list. BinarySearch has a runtime of Theta (log(n)) in all cases. (a) Consider the following two search algorithms: procedure Search(x, a_1, ..., a_n) return LinearSearch(x, a_1, ..., a_n) procedure Search2(x, a_1, ..., a_n) s_1, ..., s_n = SmartSort*(a_1, ..., a_n) return BinarySearch(x, s_1, ..., s_n) (* Assume that Smart Sort has a runtime of Theta (n log(n)) in all cases.) i. Use Theta notation to describe the runtimes of Search1 and Search2 in the best case. Which algorithm is more efficient in the best case? Justify your answers. ii. Use Theta notation to describe the runtimes of Search1 and Search2 in the worst case. Which algorithm is more efficient in the worst case? Justify your answers.Explanation / Answer
Please give the thumbs up, if it is helpful for you. Thank you!!
Answer i)
Best Case:
Search1 runtime is O(1)
Search2 runtime is
O(nlog(n)) + O(log(n)) => O(nlog(n))
Search1 is more efficient in the best case because Search1 algorithm is taking O(1)
runtime for best case and Search2 is taking atleast O(nlog(n)) for Smart scan to sort the
elements first in all cases.
Hence, Search1 is more efficient.
Answer ii)
Worst Case:
Search1 runtime is O(n)
Search2 runtime is
O(nlog(n)) + O(log(n)) => O(nlog(n))
Search1 is more efficient in the Worst case also because Search1 algorithm is taking O(n)
runtime to run and Search2 is taking atleast O(nlog(n)) for Smart scan to sort the
elements first in all cases.
Hence, Search1 is more efficient.
If the elements will already sorted that means if we remove SmartSort from the Search2
then in this case Search2 will be efficient.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.