Given a positive real number and a nonnegative integer , we call an array A of n positive real numbers (,)-sorted if the number of pairs of elements Ai, Aj such thatiAj isboundedby,i.e.,

Here 1[Ai>Aj] = 1 if Ai > Aj, otherwise 1[Ai>Aj] = 0.

1. (a) Design an efficient divide and conquer algorithm to decide whether a given array A con-

   taining n positive real numbers is (,)-sorted.

2. (b) Prove correctness of your algorithms.

3. (c) Provide time complexity analysis of your algorithm (sub-optimal algorithm or sub-optimal analysis may receive partial points).

3. (7+5+4=16 points) Given a positive real number y and a nonnegative integer , we call an array A of n positive real numbers (7,0)-sorted if the number of pairs of elements Ai, Aj such that i Aj is bounded by d, i.e., n- n E 1[A;>yA;] 58. i=1 j=i+1 Here 1[A;>xAj] = 1 if A; > YAj, otherwise 1[A;>xAj] = 0. = (a) Design an efficient divide and conquer algorithm to decide whether a given array A con- taining n positive real numbers is (7,5)-sorted. (b) Prove correctness of your algorithms. (c) Provide time complexity analysis of your algorithm (sub-optimal algorithm or sub-optimal analysis may receive partial points)