Understanding recurrence for running time

Question

I'm doing the exercises in Introduction to Algorithm by CLRS. This is not graded homework or anything, I'm just trying to understand the problem.

The problem is as follows:

We can express insertion sort as a recursive procedure as follows. In order to sort A[1..n], we recursively sort A[1..n-1] and then insert A[n] into the sorted array A[1..n-1]. Write a recurrence for the running time of this recursive version of insertion sort.

The solution to the problem:

Since it takes O(n) time in the worst case to insert A[n] into the sorted array A[1. .n −1], we get the recurrence T(n) = O(1) if n = 1 , T(n−1)+ O(n) if n > 1 . The solution to this recurrence is T(n) = O(n^2).

So I get that if n=1, then it is already sorted, therefore it takes O(1) time. But I don't understand the second part of the recurrence: The O(n) part is the step where we insert the element being sorted into the array which takes in the worst case O(n) time - the case where we have to go through the entire array and insert at the end of it.

I'm having trouble understanding the recursive part of it (T(n-1)). Does T(n-1) mean that each recursive call we are sorting one less element of the array? That doesn't seem right.

Answer 1

Yes, it follows from:

In order to sort A[1..n], we recursively sort A[1..n-1] and then insert A[n] into the sorted array A[1..n-1]

The "recursively sort A[1..n-1]" part takes T(n-1) time (this is easy: we're defining T(n) to mean "the time it takes to sort n elements", so the time it takes to sort n-1 elements is trivially T(n-1)), while the "insert A[n] into the sorted array A[1..n-1]" part takes (worst case) O(n) time. Add them together to get

T(n) = T(n-1) + O(n)

Answer 2

I will explain what I understand with the python code for Insertion sort using recursion as follows:

def insert_sort_r(A,n)

if n==1:

    pass

else:------------------------------------ c1
    insert_sort_r(A,n-1) ---------------- T(n-1)

    key = A[n-1]------------------------- c2
    i = n-2 ------------------------------c3

    while i>-1 and A[i] > key:------------c4*(n)
        A[i+1] = A[i]---------------------c5*(n-1)
        i = i-1---------------------------c6*(n-1)
    A[i+1] = key--------------------------c7

The time taken for each step is represented by the "c" values while and the number of steps taken is also shown. We represent the time taken for sorting (n-1) elements in the step "insert_sort_r(A,n-1)" as T(n-1) because we do not know exactly what will this value be in terms of n. This is the idea of recursion. To represent the equation for case when value is n with case when value is (n-1).