analysis of algorithms question?? you can use the kth largest algorithms from pa

Question

analysis of algorithms question?? you can use the kth largest algorithms from page 1 and page 2 to find the median of list. Analyze the worst case scenarios for both of these algorithms in finding the median The algorithm for this process is. FindKthLargest( list, N, K) // list the values to look through the size of the list the element to select for i = 1 to K do largest = list [1] largestocation = 1 for j = 2 to N-(1-1) do if list j]largest then largest = list [j] largest!ocation = j end if end for Swap( list (N-(-1), list[largestLocation] ) end for return largest What is the complexity of this process? On each pass, we initialize largest to the first element of the list, and then we compare largest to every other

Explanation / Answer

for 1st Algorithm

   Since there is 2 loops, outer loop goes from i = 1 to K and inner loop goes for 2 to N-(i-1);

in worst the outer loop run for K times and inner loop will run for 2 to N+1 - i times where 1 <= i <= K;

=> Time Complexity is
(N-1) + (N-2) + (N-3) ...........(N-K)
=> K*N - (1+2+3..K)
=> K*N - (K*(K+1)/2)
O(K*N - (K*(K+1)/2))
=> O(K*N);



2nd algorithm

each time in a recursion the array is divide into two half and we discard one half based on the conditions,
so the recursion functions are called (Log N times).
Also in each recursion there is partion function which is O(N);
so Overall COmplexity is
O(N*log N);


   

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

---

---

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