a) Consider the following pseudocode (shown on the next page) for a quicksort algorithm with intelligent pivot selection (shown in blue). Rather than arbitrarily choosing the middle element of the array as the pivot, this intelligent pivot selection guarantees that at least 1/3 of numbers in the array are less than the pivot and at least 1/3 are greater than the pivot. You are not given the implementation of the intelligent pivot selection, but you know that it runs in O(log N) time. Write the recurrence relation for the worst-case time complexity of this modified quicksort algorithm. You may use big o notation as a function of the number of items in the array N. (15 points) Partition (numbers, lowIndex, highIndex) { // Pick middle element as pivot midpoint = lowIndex + (highIndex - lowIndex) / 2 pivot = ChoosePivot (numbers) // O(log N) pivot selection algorithm done = false while (!done) { // Increment lowIndex while numbers[lowIndex] = highIndex) { done = true } else { // Swap numbers[lowIndex] and numbers [highIndex] temp = numbers[lowIndex] numbers [lowIndex] - numbers[highIndex] numbers [high Index] = temp // Update lowIndex and highIndex lowIndex += 1 highIndex -= 1 } } return highIndex } Quicksort (numbers, lowIndex, highIndex) { // Base case: If the partition size is 1 or zero // elements, then the partition is already sorted if (lowIndex >= highIndex) { return } // Partition the data within the array. Value lowEndIndex // returned from partitioning is the index of the low 1/ partition's last element. lowEndIndex = Partition(numbers, lowIndex, highIndex) // Recursively sort low partition (lowIndex to lowEndIndex) // and high partition (lowEndIndex + 1 to highIndex) Quicksort(numbers, lowIndex, lowEndIndex) Quicksort(numbers, lowEndIndex + 1, high Index) } a) Consider the following pseudocode (shown on the next page) for a quicksort algorithm with intelligent pivot selection (shown in blue). Rather than arbitrarily choosing the middle element of the array as the pivot, this intelligent pivot selection guarantees that at least 1/3 of numbers in the array are less than the pivot and at least 1/3 are greater than the pivot. You are not given the implementation of the intelligent pivot selection, but you know that it runs in O(log N) time. Write the recurrence relation for the worst-case time complexity of this modified quicksort algorithm. You may use big o notation as a function of the number of items in the array N. (15 points) Partition (numbers, lowIndex, highIndex) { // Pick middle element as pivot midpoint = lowIndex + (highIndex - lowIndex) / 2 pivot = ChoosePivot (numbers) // O(log N) pivot selection algorithm done = false while (!done) { // Increment lowIndex while numbers[lowIndex] = highIndex) { done = true } else { // Swap numbers[lowIndex] and numbers [highIndex] temp = numbers[lowIndex] numbers [lowIndex] - numbers[highIndex] numbers [high Index] = temp // Update lowIndex and highIndex lowIndex += 1 highIndex -= 1 } } return highIndex } Quicksort (numbers, lowIndex, highIndex) { // Base case: If the partition size is 1 or zero // elements, then the partition is already sorted if (lowIndex >= highIndex) { return } // Partition the data within the array. Value lowEndIndex // returned from partitioning is the index of the low 1/ partition's last element. lowEndIndex = Partition(numbers, lowIndex, highIndex) // Recursively sort low partition (lowIndex to lowEndIndex) // and high partition (lowEndIndex + 1 to highIndex) Quicksort(numbers, lowIndex, lowEndIndex) Quicksort(numbers, lowEndIndex + 1, high Index) }