1. Suppose you have an array of n items (the \"member items\") and a separate li
ID: 3598397 • Letter: 1
Question
1. Suppose you have an array of n items (the "member items") and a separate list of k items (the "test items"). The member items are not stored in any particular order. You want to know which of the k test items belong to the set of member items. Here are two different ways to solve the problem: . Algorithm 1: Look up each test item in the array of member items, using sequential search. . Algorithm 2: Sort the array of member items, using an optimal comparison- based sorting algorithm, and then look up each test item in the array of member items using binary search Answer the following questions, and briefly justify your answer to each part. (a) What is the worst-case running time of Algorithm 1 (asymptotically, in terms (b) What is the worst-case running time of Algorithm 2 (asymptotically, in terms (c) For a given value of n, for what values of k is Algorithm 2 at least as efficient as of n and k)? of n and k)? Algorithm 1? (Express your answer using asymptotic notation, in terms of n).Explanation / Answer
a) k.O(n) -> as we have k test items and for each test item we have to check all member items, so for each item O(n) and for k items k.O(n)
b) k.O(log n) -> as we have k test items and for each test item we have to do binary search i.e. dividing the array and gets the bibary logarithm time, so for each item it takes O(log n) and for k items k.O(log n) =>O(k.log n)
c) n should be the middle elements in the array (after dividing also), those are efficient in binary seacrh tha linear search. for example let us take array of size 10, element in 5, 2, 7 are more efficent. O(log n) is the asymtotic notation.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.