algorithm - 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

使用二分查找找到 A[N] 的正确位置，将其添加到排序列表中

• n

在找到正确的位置后，它需要移动值来为 A[N] 腾出位置。

Answer 2

Let T(n) be the runtime of the algorithm described for an array of n elements. First, it recursively calls itself on the first n-1 elements, giving us a cost of T(n-1). Then, it uses binary search to find the position of the element at original position n, thus taking log(n-1) time. Finally, it shifts the elements (at most n-1 of them) to make space for the new one, which requires at most n steps.

Putting the pieces together, we get T(n) <= T(n-1) + log(n-1) + n - 1. Finally, since you did not specify the base case, I am assuming the algorithm just does nothing on an empty list (thus trivially sorting it) and then get T(0) = 0.