The following is a multiple choice question: Let C(n) be average number of compa

Question

The following is a multiple choice question: Let C(n) be average number of compares in quicksort algorithm. Which of the following is the correct recurrence of C(n)? A. nC(n) = (n+1) C(n-1) + n B. C(n) = (n+1)/n C(n-1) + 2 C. C(n) = (n+1) C(n-1) + 2n D. C(n) = (n+1)/n C(n-1) + 2/n This is the quicksort algorithm mentioned: private void quicksort(int[] a, int lo, int hi) { if (hi <= lo) return; int i = lo-1, j = hi; int t, v = a[hi]; while (true) { while (a[++i] < v) ; while (v < a[--j]) if (j == lo) break; if (i >= j) break; t = a[i]; a[i] = a[j]; a[j] = t; } t = a[i]; a[i] = a[hi]; a[hi] = t; quicksort(a, lo, i-1); quicksort(a, i+1, hi); }

Explanation / Answer

The correct recurrence of C(n) for the given quick sort code is as follows:

C. C(n) = (n+1) C(n-1) + 2n

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

---

---

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