Consider the following recurrence for a function T that takes on nonnegative values and is defined on integers ≥ 1:T(n) ≤ 5 if 1 ≤ n  ≤ 4 or ≤T(7n/10) + T(n/5) + 3n if n > 4. Prove that T(n) is O(n). You should present a particular constant c and prove that T(n) ≤ c · n for all n ≥ 1.

Motivation: This recurrence actually comes up in the following situation. Say we wish to find the median of n distinct elements, using as few comparisons as possible. Recall that the median is an element with rank the floor of n/2 .More generally, say we wish to find the k-th smallest of n elements. We could sort the n numbers but this takes about n log n comparisons. Instead we do the following which, by the theorem proven in this question, uses O(n) comparisons:

Divide the elements up into groups of 5 (don’t worry now about what to do if n isn’t divisible by 5); find themedian of each group of 5, using a linear in n number of comparisons in total. This gives us about n/5 median points. Recursively find the median of these median points using about T(n/5) comparisons; call this element b. Using a linear in n number of comparisons, compare every element to b; let S1 be the set of elements ≤ b, and let S2 be the set of elements > b. Because of the way b was chosen, each of S1 and S2 must have at most 7n/10 elements.If k ≤ |S1|, then recursively find the k-th smallest element of S1, otherwise recursively find the (k − |S1|)-th smallest element of S2; this takes at most T(7n/10) comparisons.

ComputerScienceExpert

(11)

Status NEW Posted 03 May 2017 04:05 AM My Price 9.00

-----------

Attachments

file 1493787256-Solutions file 2.docx preview (51 words )

H-----------ell-----------o S-----------ir/-----------Mad-----------am ----------- Th-----------ank----------- yo-----------u f-----------or -----------you-----------r i-----------nte-----------res-----------t a-----------nd -----------buy-----------ing----------- my----------- po-----------ste-----------d s-----------olu-----------tio-----------n. -----------Ple-----------ase----------- pi-----------ng -----------me -----------on -----------cha-----------t I----------- am----------- on-----------lin-----------e o-----------r i-----------nbo-----------x m-----------e a----------- me-----------ssa-----------ge -----------I w-----------ill----------- be----------- qu-----------ick-----------ly -----------onl-----------ine----------- an-----------d g-----------ive----------- yo-----------u e-----------xac-----------t f-----------ile----------- an-----------d t-----------he -----------sam-----------e f-----------ile----------- is----------- al-----------so -----------sen-----------t t-----------o y-----------our----------- em-----------ail----------- th-----------at -----------is -----------reg-----------ist-----------ere-----------d o-----------n -----------THI-----------S W-----------EBS-----------ITE-----------. ----------- Th-----------ank----------- yo-----------u -----------

Not Rated(0)

• Buy Answer