Description

Consider the following functions for problems 1 and 2. void selectionSort(int array[]) { sort(array, 0); } void sort(int[] array, int i) { if (i < array.length - 1) { int j = smallest(array, i); int temp = array[i]; array[i] = array[j]; array[j] = temp; sort(array, i + 1); } } int smallest(int[] array, int j) { if (j == array.length - 1) return array.length - 1; int k = smallest(array, j + 1); return array[j] < array[k] ? j : k; } 1. Draw the recursion tree for selectionSort when it is called for an array of length 4. Show the activations of selectionSort, sort and smallest in the tree. 2. Determine a formula that counts the numbers of nodes in the recursion tree. What is Big-  for execution time? Determine a formula that expresses the height of the tree. What is the Big- for memory?