Compute the asymptotic runtimes of the variants and use this to justify which is

Question

Compute the asymptotic runtimes of the variants and use this to justify which is best:

I need help!

2. Variants of quicksort (6 points) Suppose company X has created 3 new variants of quicksort but, because they are unsure which is asymptotically best, they have hired you to analyze their runtimes. Compute the asymptotic runtimes of the variants and use this to justify which is best: Variant 1: Partitioning the array still takes (n) time but the array will always be divided into (at least) a 10% and 90% portion. . Variant 2: Partitioning the array now takes (n1.1) time but the array will always be divided perfectly in half. Variant 3: Partitioning the array now only takes (V n) time but all of the numbers except the pivot will be partitioned into a single array. Hint: It may help to know that VTie (n3/2) and that log n all c 0. o(r) for

Explanation / Answer

Variant 1 :

This will form the recurrance as

T(n) = T(n/10) + T(9n/10) + O(n)

Solving the above recurrance we get T(n) = O(n log n) . It forms the average case of Quick Sort

Variant 2 :
This will form the recurrance as

T(n) = 2T(n/2) + O(n)
This is similar to Merge Sort where array is divided into half each time


How to come up with recurrance: everytime the array will be divided into half so we have two subproblems of Size n/2
Hence we get 2T(n/2) and O(n) is for Partition process
Therefore we write
T(n) = 2T(n/2) + O(n)
Solving the above recurrance we get T(n) = O(n log n)

Variant 3 :
This will form the recurrance as

T(n) = T(n-1) + O(n)
This is when partition is one side and whole array is other side
Solving the above recurrance we get T(n) = O(n2)

How to come up with recurrance: evrytime the array will be divided into 1 and n-1 element so we have two subproblems one of size 1 and the other of size n-1 , T(1) = 1 its constant can be ignored
Hence we get T(n-1) and O(n) is for Partition process
Therefore we write

T(n) = T(n-1) + O(n)
Thsi forms the Worst case when the array is sorted so that pivot takes one half and resulst in worst case.

Thanks, let me know if you need amore explanation or if there is anything please let me know. Comment and I will surely respoind

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

---

---

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