We want to sort an array A[1n] using quicksort, where n is a power of 2. Suppose

Question

We want to sort an array A[1n] using quicksort, where n is a power of 2. Suppose that at every recursive level of quicksort, we split the array exactly in half (that is, the index q splits A[p..r] into two subarrays A[p..q] and A[q +..r] with same number of elements ( r - p + 1 ) / 2 ) .What is the running time of quicksort in this case? Please express this running time in O - notation, using the best asymptotic bound you can find. Justify your answer. (Hint: What is the height of the recursive calls tree in this case?) If n is not a power of 2. does the best asymptotic hound on the running time for quicksort with this half-and-half split change?

Explanation / Answer

In first case running time is O(nlogn) If N is not power of 2 then it does not effect asymptotic bound.

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

---

---

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