Question

Which of these recurrence relations correctly captures the worst case running time of insertion sort? O T(n) = T(n − 1) + cn OT(n) T(n − 1) + c п OT(n) =T () + cn 2 OT(n) T(n − 1) +on?

Answer 1

The recurrence relation that correctly captures the worst case running time of insertion sort is O(T(n) = T(n − 1) + cn), where T(n) represents the running time for a list of size n and cn represents the time it takes to insert an element into a sorted list of n-1 elements in the worst case scenario. In each step of the algorithm, the remaining unsorted elements are inserted into the sorted portion of the list, resulting in a recurrence relation that depends on the size of the remaining unsorted list. This relation is linear and corresponds to the worst case scenario, where each element in the unsorted list must be inserted into its correct position in the sorted list, resulting in a time complexity of O(n^2). Therefore, the correct option is OT(n) = T(n − 1) + cn.