Question

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

Solution)

A)

When entire or all elements in a givened list of length N are equal or equivalent,it is the finest or best case of Insertion Sort. So that the O(N) is the running time of insertion sort. Insertion sort require only 1 full traversal of the array to complete the sort.

B)

In Merge Sort, there are 3 steps those are 1)Divide step, 2)the Conqer step and the 3)Combine step.The time complexity of first step Divide step is O(1), the time complexity of second step Conquer step is O(log n) and the time complexity of third step Combine step is O(n), If entire elements of the list are equal or equivalent, O(log N). Here the base of logarithm is 2. Let Assume N is a power of 2, say for instance N = 2^V, the time complexity is O(V), where V is a very little number when comparing to N, if N tending to big. Thus for large lists, so that the time complexity of merge sort is minor or negligible.

I HOPE THIS ANSWER WILL HELP YOU PLEASE DO UP VOTE THAT MEANS A LOT TO ME THANK YOU.