1) Suppose you have an array of n items (the “member items”) and a separate list
ID: 3595287 • 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 comparisonbased 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 of n and k)?
B) What is the worst-case running time of Algorithm 2 (asymptotically, in terms of n and k)?
C) For a given value of n, for what values of k is Algorithm 2 at least as efficient as Algorithm 1? (Express your answer using asymptotic notation, in terms of n).
Explanation / Answer
In the worst case analysis, we calculate upper bound on running time of an algorithm. We must know the case that causes maximum number of operations to be executed. For Sequential Search, the worst case happens when the n items(member items) are searching every element in k test items. So the member item element is not present in the k test items, It will check all the elements in the array of test items. In the same way n items need to check n times . Therefore, the worst case time complexity of linear search according to the specified scenario is (n*n). In case two if we sort one list of elements it could be take very less time then Algorithm one.Why because half of the time we can cover while searching for an element in a sorted list instead of search all the elements with n times. In Binary search if we want to search for an element we don’t need to search all elements, we can only search half of the list present in the list. So it could be take very less time. For the second Algorithm the worst case time complexity for this scenario is (n*n/2) In this case we can consider all the elements are efficient if we use second Algorithm to search k test items in a sorted elements of n member items by using binary search. Definately the second Algorithm is efficient than the first Algorithm.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.