Understanding Repeatability for Runtime

Question

I am doing the exercises in the Introduction to Algorithm section of CLRS. This is not a classified homework or anything else, I'm just trying to understand the problem.

The problem is this:

We can express insertion sorting as a recursive procedure as follows. In 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 repeat for the runtime of this recursive version of the sort insert.

Solution:

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

So, I get this if n = 1, then it is already sorted, so it takes O (1) time. But I don’t understand the second part of the repetition: Part O (n) is the step at which we insert an element that is sorted into an array that takes the worst time O (n) is the case when we need to go through the whole array and insert it at the end .

It's hard for me to understand the recursive part (T (n-1)). Does T (n-1) have that each recursive call we sort by one smaller element of the array? This does not seem right.

Answer 1

Yes, this follows from:

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 the time T (n-1) (it's easy: we define T (n) as the "time it takes to sort n elements", so the time it takes to sort n-1 elements, trivially T (n-1)), and 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 by using python code to sort Insertion 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 "c" values, and the number of steps taken is also shown. We represent the time taken to sort (n-1) items in the step "insert_sort_r (A, n-1)" as T (n-1), because we do not know exactly what this value will be in terms of n. This is the idea of ​​recursion. Provide an equation for the case where the value of n is in the case where the value is (n-1).