Analysis of random splitters Flashcards
What is the goal of the median-finding problem?
To find the middle element of a sorted set of numbers.
What is the Select algorithm used for?
Select(S, k) finds the kth largest element in a set S of n numbers.
What is the base case for the Select algorithm?
If |S| = 1, then the single element in S is returned.
Why is a ‘splitter’ chosen in the Select algorithm?
A splitter divides the set S into subsets S- and S+, allowing the search for the kth largest element to focus on a smaller subset.
What is the expected time complexity of the Select algorithm?
The expected time complexity is O(n).
How does the choice of a splitter affect the Select algorithm’s performance?
A well-centered splitter significantly reduces the size of the subset considered in recursive calls, improving performance.
What happens if the splitter in Select is the minimum element?
The algorithm performs poorly, as the recursive call reduces the subset size by only one element.
Why is randomization used to choose the splitter in Select?
Randomization ensures a high probability of choosing a well-centered splitter, avoiding worst-case scenarios.
What is the probability of selecting a ‘central’ splitter in the Select algorithm?
The probability is 1/2, as half of the elements in the set are central.
What is the recurrence for Select when random splitters are used?
T(n) ≤ T((3/4)n) + cn, which resolves to O(n) using geometric series analysis.
What is the Quicksort algorithm?
Quicksort is a sorting algorithm that uses a random splitter to divide a set into two subsets, recursively sorting each.
What is the worst-case running time of Quicksort?
The worst-case running time is O(n^2), occurring when splitters are poorly chosen (e.g., smallest elements).
What is the expected running time of Quicksort?
The expected running time is O(n log n), achieved through randomization of splitters.
What is a central splitter in Quicksort?
A central splitter divides the set so that each subset contains at least a quarter of the elements.
What is the role of randomization in Quicksort?
Randomization increases the likelihood of selecting central splitters, ensuring efficient sorting.
What is Modified Quicksort?
Modified Quicksort finds a central splitter before making recursive calls, ensuring balanced division of subsets.
What is the expected time spent in one phase of Modified Quicksort?
The expected time spent in one phase, excluding recursive calls, is O(|S|), where S is the set size.
How many iterations are expected to find a central splitter in Modified Quicksort?
The expected number of iterations is 2, as half of the elements are central.
What is the recurrence for Modified Quicksort’s time complexity?
T(n) ≤ 2T((3/4)n) + cn, leading to an expected running time of O(n log n).
How does the number of subproblems relate to the phase type in Modified Quicksort?
There are at most (4/3)^j subproblems of type j, where j is the phase type.
What is the difference between Quicksort and Modified Quicksort?
Quicksort accepts all splitters, while Modified Quicksort retries until finding a central splitter.
What is the purpose of splitting the input set in Quicksort?
Splitting organizes elements smaller than the splitter into one subset and larger elements into another for efficient sorting.
How does recursion in Quicksort handle subsets?
Quicksort recursively sorts subsets created by splitting, then combines them with the splitter to form the sorted output.
What is the intuition behind the efficiency of Quicksort?
Randomly chosen splitters are likely to balance subsets, leading to efficient sorting on average.
What is the convergence property of Quicksort’s recurrence?
The recurrence forms a geometric series, ensuring O(n log n) expected time for sorting.
What is the geometric series’ role in analyzing Quicksort?
The geometric series bounds the total work across recursive calls, showing the algorithm’s efficiency.
How does Modified Quicksort guarantee balanced recursive calls?
By ensuring splitters are central, Modified Quicksort reduces each subset by at least 25%.
What is the relationship between randomization and performance in Quicksort?
Randomization reduces the likelihood of worst-case scenarios, maintaining expected O(n log n) performance.
What happens when Modified Quicksort updates the splitter?
It retries splitting with a new random splitter until a central splitter is found.
How is the running time of Modified Quicksort bounded?
The running time is bounded by summing the expected costs of processing subsets of decreasing size, yielding O(n log n).
