Question
When doing Quick-Select and Quick-Select, it is desired to have a good pivot which is almost in the middle of the sorted array. When doing
When doing Quick-Select and Quick-Select, it is desired to have a good pivot which is almost in the middle of the sorted array. When doing the average-case analysis of Quick-Select, we considered a good and a bad case; the good case happened when the pivot was among the half middle items of the sorted array, i.e., we had n/4 i < 3n/4 (i is the index of pivot in the partitioned array). In our analysis, we provided an upper bound for the time complexity of the algorithm in the good case and showed that T(n) T(3n/4) + cn in these cases for some constant c. Since the good case happened with probability 1/2, we could prove that the algorithm runs in linear time on average (see the recursion slide 10 of lectures on selections). Change the definition of the good case and assume the good case happens when we have n/10 i < 9n/10. Provide an upper bound for T(n) and use that to show that Quick-Select runs in O(n). Hint: start by calculating the probability of good case and bad case happening.
Step by Step Solution
There are 3 Steps involved in it
Step: 1
Get Instant Access to Expert-Tailored Solutions
See step-by-step solutions with expert insights and AI powered tools for academic success
Step: 2
Step: 3
Ace Your Homework with AI
Get the answers you need in no time with our AI-driven, step-by-step assistance
Get Started