Question

Using the worst case scenario for a recursive insertion sort on an array of 5 elements {5, 4, 3, 2, 1}

Determine a formula that counts the numbers of nodes in that recursion tree. What is the Big O for execution time.
Determine a formula that expresses the height of the recursion tree. What is the Big O for memory?

Answer 1

FOR example the array is

int A[]={ 6, 5,4,3,2,1. };

HENCE the recursion calls will be as follow :-

then according to code:

void RecursiveSort(int arr[], int n)

{

    // Base case

    if (n <= 1)

        return;

    RecursiveSort( arr, n-1 );

    int last = arr[n-1];

    int j = n-2;

  

    while (j >= 0 && arr[j] > last)

    {

        arr[j+1] = arr[j];

        j--;

    }

    arr[j+1] = last;

}

here we can see that the we recursively call the sub array of size-1 until we reach the single element from this it's clear that

there is [SPACE SIZE == O(n) ] space stack required ,thus the height of three is same as stack size, but there this tree is linear tree

so the time complexity is same as iterative sort O(n²)