(2) Shearsort. [a] When the numbers being sorted are restricted to the set {0, 1), we showed that the end state consists of at most one mixed row of Os and 1s. Derive the maximum number of steps required (each row and each column sort counts as a separate single step) to execute Shearsort, assuming an 8 x 8 array. [b] The maximum number of steps required to sort an arbitrary set of numbers is no greater than the maxi- mum required to sort an arbitrary sequence of elements from {0, 1}. How would you show that? (Just saying 0-1 Lemma" is not enough: you need to show more detail in your argument.) (3) Consider the recurrence (here l is a whole number greater than 1): T S 2 2T(n/2) +n if n if n = 2 = 2 Prove by induction that the solution of this recurrence is T(n) = nlgn. (2) Shearsort. [a] When the numbers being sorted are restricted to the set {0, 1), we showed that the end state consists of at most one mixed row of Os and 1s. Derive the maximum number of steps required (each row and each column sort counts as a separate single step) to execute Shearsort, assuming an 8 x 8 array. [b] The maximum number of steps required to sort an arbitrary set of numbers is no greater than the maxi- mum required to sort an arbitrary sequence of elements from {0, 1}. How would you show that? (Just saying 0-1 Lemma" is not enough: you need to show more detail in your argument.) (3) Consider the recurrence (here l is a whole number greater than 1): T S 2 2T(n/2) +n if n if n = 2 = 2 Prove by induction that the solution of this recurrence is T(n) = nlgn