Median-of-medians algorithm partitions input into groups

Assignment Help Programming Languages

Reference no: EM1371465

Now, recall median-of-medians algorithm to solve selection problem. Complete following exercises.

1. To guarantee O(n) time, the median-of-medians algorithm makes recursive calls only when the input size n ≥ 80; however, the choice of this constant 80 is somewhat arbitrary. In fact, we can still achieve O(n) time even if we make recursive calls on smaller input. What is the smallest input size with which we can make a recursive call, while maintaining O(n) time? Carefully justify your answer.

2. The median-of-medians algorithm partitions the input into groups of 5 elements, but it also works if we partition the input into groups of 7. Prove carefully that this modified algorithm still runs in O(n) time.

Reference no: EM1371465

Questions Cloud

How long it take for the police car to catch up with speeder : A 5 m x 12 m swimming pool slopes linearly from a 1.20 m depth at one end to a 3.40 m depth at the other. What is the mass of water in pool.

Illustrate jon economic costs while attending college : At university he attended, he spent $2,000 on books, $1,000 on cough medicine and earned $12,000 as an economics instructor. Illustrate what were Jon's economic costs while attending college.

Explain and consider a poisson probability distribution : Explain and Consider a Poisson probability distribution in a manufacturing process with an average of 3 flaws every 100 feet

What is the breaking strength of the string : A grindstone of a radius 4 m is firstly spinning with a radius of 8 rad/s. The angular speed is then increased to 12 rad/s over next 4.0 seconds. Suppose that the angular acceleration is constant. What is the average angular speed of grindstone.

Median-of-medians algorithm partitions input into groups : Median-of-medians algorithm to solve selection problem. Complete following exercises. Median-of-medians algorithm partitions input into groups of 5 elements, but it also works if we partition input into groups of 7.

What is minimum coefficient of static friction of tires : A street lamp weighs 152N. It is supported equally by two wires that form the angle of 120° with each other. What is the tension of each of these wires.

Illustrate what best depicts se events on market for recycle : Illustrate what best depicts se events on market for recycled materials. Price remained constant.

Technology and job loss : When people lose their jobs, it helps people get a better hold on life and help them make changes themselves through personal growth. Explain.

Iscuss a company two short run options : Why are Average Cost Curves U-shaped? Illustrate what is Law of Diminishing Returns. Discuss a company's two short run options.

User Account

All Pages