Question

Plz show the ans step by step

-Q8. [8 marks] You are given n distinct integers in an array arr. For finding the k-th smallest element in this array, there is a random algorithm shown as below. Based on this algorithm, answer the following questions. Algorithm kthSmallest (arr, left, right, k) 1: if left == right 2: return arrleft 3: pivot = random(left, right) 4: pivotnewpos = partition(arr, left, right, pivot) 5: while pivotnewpos left+ right-left+1), left + (right-left+1)] 6: pivot = random(left, right) 7: pivotnewpos = partition (arr, left, right, pivot) 8: if pivotnewpos-left == k-1 9: return arr[pivotnewpos] 10: elseif pivotnewpos-left > k-1 11: return kthSmallest (arr, left, pivotnewpos-1, k) 12: else 13: return kthSmallest(arr, pivotnewpos+1, right, (k-1)-(pivotnewpos-left)) - (i). [4 marks) During an invocation of kthSmallest(arr, left, right, k), we assume that the size of the subarray arr[left...right), i.e., right-left+1, is an integer n that is multiple of 3. For this invocation, calculate the expected number of the basic opera- tion random(left, right) executed from Lines 1-7. Besides, what is the expected run- ning cost for Lines 1-7 in terms of Big-Oh? Justify your answer. (Refer to CSC12100C- Lecture 15-16 Pages 34-36 for functions of random, partition and definitions of the pivot and pivotnewpos. - (ii). [4 marks] Let T(n) be the expected number of comparisons in the above algo- rithm for finding the k-th smallest element in an array of size n. Derive the recurrence of T(n) and analyze the asymptoic complexity of T(n) in terms of Big-Oh. Justify your answer. (Hint. Consider the largest size of the subarray arr[left, pivotnewpos-1] (or arr(pivotnewpos+1, right]) when we do the recursion in Line 11 (or Line 13))

Answer 1

(i) The instruction "random(left,right)" will execute repeatedly as long as the index "pivot" returned by this function is not within the rangle of middle 1/3 of the array.

Hence the probability that index "pivot" is within the range of n/3 possible indices out of n possible indices = $\frac{(n/3)}{n} = 1/3$

Hence probability that random(left,right) returned the desired result in k trials will be $(2/3)^{k-1}(1/3)$ i.e. failure happens k-1 times followed by success at kth trials.

Hence expected number of trials will be $\sum_{k=1}^{\infty}k*\text{(Probability of success in k trials)} \\= \sum_{k=1}^{\infty}k (2/3)^{k-1}(1/3) = 2* \sum_{k=1}^{\infty}k/3^k = 2*1/(1-1/3)^2 = 4.5$

Hence expected number of trials is 4.5 = O(1)

Since the function "partition(arr, left, right, pivot)" will executing in O(right-left) time will be repeated 4.5 times i.e. O(1).

Hence if the size of array arr[left.....right] is n then the recurrence relation will be

T(n) = (4.5)*n = 4.5n = O(n)

Hence the time complexity of code from line 1-7 is O(n).

ii. Since the function kthSmallest with input array of length n will always recurse over the subarray of length atmost 2n/3. And there is O(n) complexity at each recursive due to code from line 1 to line 7.

Hence the recurrene relation of time complexity will be

T(n) = T(2n/3) + O(n)

which will solve to T(n) = O(n)

Hence time complexity of this code is O(n).

Please comment for any clarification.