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.

Hamburger

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)

Deflexed

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).

Pfeiffer

This answer is a bit of a hot mess. The formatting is messed up and it is unclear what you are trying to get across. – Stouthearted

Please specify which part of this explanation you did not understand so that I can elaborate upon that. – Pfeiffer

"The formatting is messed up and it is unclear what you are trying to get across." – Stouthearted

I hope the formatting is clear now. So the question was he did not understand the case when n>1. For n>1 there are two parts in the running time equation. One is T(n-1) and the other one is O(n). So what I did was show how these two parts are coming with the help of a python code. And also once you solve this recursion it is seen that it's solution is a quadratic polynomial which is why the overall running time is O(n^2). Hope this is clear to you now. If you want to see how the recursion is solved please let me know. – Pfeiffer

Explanation and clarification should be in the body of the answer. Comments can be removed. i.e., don't explain it to me. Explain it to everyone. – Stouthearted

This is exactly what I explained in the body too. Since you had difficulty understanding it I elaborated it further is all. If anyone else has trouble understanding I will include the same in the body. – Pfeiffer

All I'm saying is that when I scan over your answer in the context of the question, I see a wall of text that doesn't seem to match expectations. I'm making suggestions for clarity and readability. You could, for example, try more whitespace, and using inline formatting to clarify your logic. SO isn't about being "right". It is about crafting good Q & A. – Stouthearted