Recurrence equation for sorting algorithm

Question

I have the following question on a homework assignment and I'm not sure how to approach it

Assume we have the following sorting algorithm:

To sort an array of size N(A[1…N]), the algorithm will do the following:

1. Recursively, Sort the first N-1 elements A[1…N-1]
2. Use binary search to find the correct place of A[N] to add it to the sorted list. After finding the correct place, it will need to shift the values to make place for A[N].

Write the detailed recurrence equation for this algorithm (do not omit any terms).

Answer 1

where C is some constant.

Let's see where each term comes from in the n > 1 case:

• T_{n - 1}

Recursively, Sort the first N-1 elements A[1…N-1]

• log n

Use binary search to find the correct place of A[N] to add it to the sorted list

• n

After finding the correct place, it will need to shift the values to make place for A[N].