Consider the deterministic (i.e., non-randomized) quicksort which takes the first element as a pivot and uses the partition routine that we covered in class on the quicksort slides. Let's consider another almost-best case for quicksort, in which our chosen pivot always splits the array into a 1/3 portion and a 2/3 portion. (1) Give the runtime recurrence for this almost-best case (2) Use the recursion tree method to argue why the runtime recurrence solves to (n log n). (Yon don't need to prove that this guess is correct using big-Oh induction) (3) Give a sequence of 13 distinct numbers that cause this almost-best case behavior (i.e., the array is split by the function partition such that there are 4 elements on the left side, then the pivot, and finally the last 8 elements on the right side.)