Question

The following is the code for a recursive implementation of Insertion Sort. void insertionSort(int array(1) insert (array, 1); void insert(int[] array, int i) if (i < array.length) int value = array[i]; int j = shift (array, value, i); array[j] = value; insert (array, i + 1); int shift(int[] array, int value, int i) int insert = i; if (i > 0 && array[i - 1] > value) array[i] = array[i - 1]; insert = shift (array, value, i - 1); return insert; Determine a formula that counts the number of nodes in the recursion tree when the above implementation is given an array of 5 elements sorted in reverse order {5, 4, 3, 2, 1).

Here is the recursion tree for the above:

I need to know the formula that counts the nodes in that recursion tree.

An example:
the recursion tree for a selection sort with an array of 4 in the worst case scenario looks like this:

That is the type of solution I am looking for. Please determine the formula to count the number of nodes in the recursion tree for the insertion sort with an array size of 5 (n=5) where the data is in the worst case scenario.

Please help.

Answer 1