Draw the recursion tree of this algorithm for inputs A-10, 3, 9, 4, 8, 5, 7, 6],

Question

Draw the recursion tree of this algorithm for inputs A-10, 3, 9, 4, 8, 5, 7, 6], p-1, r 8, k 2. At each non- base case node show all of the following: (1) values of all parameters: input array A, p, r & k; (2) A after Partition. At each base case node show values of all parameters: input array A, p, r & k. Beside each downward arrow connecting a parent execution to a child recursive execution, show the value returned upwards by the child execution

2. (22 points) Quicksort (a) (6 points) 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) {p & 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 Partition (A,p,r) 3 pivot Distance q-p+1 4 f k pivot Distance then return A[q] 6 else if k pivotDistance then return Quickselect(A,p,q-1,k) else return Quickselect (A,q+1,r, k-pivotDistance) Draw the recursion tree of this algorithm for inputs A-10, 3, 9, 4, 8, 5, 7, 6], p-1, r 8, k 2. At each non- base case node show all of the following: (1) values of all parameters: input array A, p, r & k; (2) A after Partition. At each base case node show values of all parameters: input array A, p, r & k. Beside each downward arrow connecting a parent execution to a child recursive execution, show the value returned upwards by the child execution

Explanation / Answer

T(n) = T(n/4) + T(n/2) + cn2 cn2 / T(n/4) T(n/2) If we further break down the expression T(n/4) and T(n/2), we get following recursion tree. cn2 / c(n2)/16 c(n2)/4 / / T(n/16) T(n/8) T(n/8) T(n/4) Breaking down further gives us following cn2 / c(n2)/16 c(n2)/4 / / c(n2)/256 c(n2)/64 c(n2)/64 c(n2)/16 / / / / To know the value of T(n), we need to calculate sum of tree nodes level by level. If we sum the above tree level by level, we get the following series T(n) = c(n^2 + 5(n^2)/16 + 25(n^2)/256) + .... The above series is geometrical progression with ratio 5/16. To get an upper bound, we can sum the infinite series. We get the sum as (n2)/(1 - 5/16) which is O(n2)

Related Questions

Navigate

• Browse (All)
• Browse D
• Subjects

---

---

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