Algorithms and Analysis a) What initial ordering of an array produces the best c

Question

Algorithms and Analysis

a) What initial ordering of an array produces the best case for a quicksort where the partitioning clement is the last in the presently considered sublist? In that case write the recurrence relation for the time T(n) to sort n elements in terms of the partitioning time (as a function of n) and times necessary to sort the two partitions, as a function of their size. b) What initial ordering of an array produces the best case for quicksort for which the middle element forms the partitioning element? In that case what is the recurrence relation?

Explanation / Answer

1)
Unsorted Array will produce the best result when pivot element is last element of the Array.

2)
When the pivot is in the middle of the Array, we have best time complexity O(n log n) for Quick Sort.
Recursion Relation :-
T(N) = 2*T(N/2) + cN;
Divide by N
T(N)/N = 2*T(N/2)/N + c;
=> T(N)/N = T(N/2)/(N/2) + c;

Telescoping
T(N)/(N/2) = T(N/4)/(N/4) + c;
  T(N)/(N/4) = T(N/8)/(N/8) + c;
...
...
...
T(2)/2 = T(1)/1 + c;

Add all equation gives us
T(N) = N + (N log N)

so time time complexity is O(Log n)*n

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

---

---

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