Question

What will be the recurrence relation of the code of recursive insertion sort?

(a) T(n) = 2T(n/2) + n

(b) T(n) = 2T(n/2) + c

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

(d) T(n) = T(n-1) + c

The question was asked in an interview for job.

The origin of the question is Sorting in section Sorting of Data Structures & Algorithms II

Answer 1

Right answer is (c) T(n) = T(n-1) + n

Easy explanation - The recurrence relation of the code of recursive insertion sort is T(n) = T(n-1) + n. It can be solved by the method of substitution and is found to be equal to n^2.