This algorithm has two base cases. Explain what the first base case that the alg

Question

This algorithm has two base cases. Explain what the first base case that the algorithm checks for

2. (22 points) Quicksort Quicksort can be modified to obtain an elegant and efficient linear (O(n)) algorithm QuickSelect for the selection problem. Quick select (A, p, r, k) Hp & r-starting and ending indexes; to find k-th smallest number in non-empty array A; 1sks(r-p+1) 1 if p r then return Alp] else 2 q Partition (A,p,r) 3 pivot Distance q-p+1 4 f k pivot Distance then return Ala] 6 else if pivotDistance then return Quickselect (Arp,q-1,k) else return Quickselect(A,q+1,r, k-pivotDistance) input A-10, 3, 9, 4, 8, 5, 7, 6], p 1, r 8, k 2.

Explanation / Answer

T(n) for first base case is On();

T(n) for worst case is O(n^2);

T(n) for best case is O(nlogn)

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

---