Question

Problem 2 (2+3 marks). Assume your sorting algorithms have to deal with lists that can potentially contain duplicates. Assume the same sorting algorithms as discussed in class / in the textbook. (a) What is the running time of Insertion Sort when all elements in a given list of length N are equal? Explain your answer. (b) Give a Θ-bound on the running time of Mergesort for the case that all elements in a given list of length N are equal (assuming N is a power of 2). Explain your answer.

Answer 1

(a)   

It is the best case of Insertion sort i.e when all the elements in a given list of length N are equal. Hence the running time of insertion sort is O(N) Insertion sort needs only one complete traversal of the array to complete the sort.

(b)

In Merge Sort, there are three steps :- the Divide step

the Conqer step

the Combine step.

The time complexity of Divide step is O(1), the time complexity of Conquer step is O(log n) and the time complexity of Combine step is O(n), If all the elements of the list are equal, O(log N). (Here the base of logarithm is 2.) Assuming N is a power of 2, say for example N = 2^M, the time complexity is O(M), where M is a very small number when compared to N, if N tends to large. Thus for larger lists, the time complexity of merge sort is negligible.