Question
Given a set of n numbers, we wish to find the i largest in sorted order using a comparison-based algorithm. Find the algorithm that implements
Given a set of n numbers, we wish to find the i largest in sorted order using a comparison-based algorithm. Find the algorithm that implements each of the following methods with the best asymptotic worst-case running time, and analyze the running times of the algorithms in terms of n and i.
a. Sort the numbers, and list the i largest.Group of answer choices
1. O(ni)
2. O(nlg(n))
3. O(n + ilg(n))
4. O(i + nlg(n))
5. O(n + ilg(i))
b. Build a max-priority queue from the numbers, and call EXTRACT-MAX i times.
Group of answer choices
1. O(i + nlg(n))
2. O(n + ilg(n))
3. O(nlg(n))
4. O(ni)
5. O(n + ilg(i))
c. Use an order-statistic algorithm to find the ith largest number, partition around that number, and sort the i largest numbers.Group of answer choices
1. O(n + ilg(i))
2. O(n + ilg(n))
3. O(nlg(n))
4. O(i + nlg(n))
5. O(ni)
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