Algorithm Fun with Medians

(a) (3 points) HALVING is the the operation that takes an array A with n distinct numbers and separates it into two half-sized3 arrays Ao and A, where all elements of Ao are smaller than all elements of A. (Note that it is not required that Ao and Ai are sorted.) Prove that HALVING can be done in linear time. (b) (5 points) An array Bli . . . n] is called a roller coaster if B[1] B3], B3] B2i1 and B[2i -11 B3], B3] B2i1 and B[2i -11