1. Suppose you have an array of n items (the \"member items\") and a separate li

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

Algorithm1:-Worst case running time is the time in which we have to go till the end of the loop. For sequential search we have worst case when we have to traverse the array(n) till the end to find the element(kth).

Linear search stated as below:-

SeqSearch(member_item[1....n],test_item[1...k]

i := 1
item found := false
while i <= n and not found do
if member_item[j] = k then item found := true end if
i := i+1
end while
return item found

let T(n)=worst case complexity

step1:- for worst case number of times while loop execute= n times...............eq1

step2:- for each iteration for while loop it take some constants c= nc...............eq2
step3:- outside loop there are some constant declaration which takes d steps

adding all the three steps we get Equation= nc+d.......eq4

Time taken for algorithm to traverse all n elements in array is (n)
So the worst case time complexity of the algorithm T(n) is O(n).

Algorithm2: - Binary search can only be applied on the array which is sorted, here let’s say the complexity of comparison based sorting algorithm is O(n * log n), so now we find the worst case complexity of binary search.

For binary case the array is divided into two equal parts and then search is performed. We can simply apply master theorem to find the complexity

Let’s say complexity for binary search is T(n), so when we divide the array into half it becomes

T(n)=t(n/2) + O(1) this relation is called recurrence relation.

After applying master theorem we get

T(n)=aT(n/b)+f(n)

Where a=1, b=2

For f(n) we can also say that f(n)=n^clog^k(n) where k=0, c=log (a base b)

Therefore

T(n)= O(n^clog^(k+1)n)=O(log(n))

When we add the complexity of both the sorting and binary search we get

T(n) = O(n*logn) + O(log(n))

T(n) = (n+1)* log(n) which is

T(n)= n(log(n)) ....(worst case complexity)

Related Questions

Navigate

• Browse (All)
• Browse 1
• Subjects

---

---

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