Explain why merge sort always achieves O(nlog n) runtime complexity. It cannot b

Question

Explain why merge sort always achieves O(nlog n) runtime complexity.

It cannot be O(n)

Explain runtime complexities in terms of big-O for the following scenarios:           

Insertion sort applied on an array where all values are equal

Bubble sort applied on an array where items are already in sorted order.

Suppose you have an array A = {8, 5, 6, 3}. Your job is to sort elements of A in increasing order. Suppose a comparison instruction takes 2 nanoseconds and an exchange (swap) instruction takes 10 nanoseconds. Design a scheme that uses minimum amount of time to achieve the sorted order. Indicate the time in nanoseconds as well. (Show your work or explain how you achieve your minimum time)                                                                    

Suppose you have an unsorted array of n distinct elements. You are required to perform n searches on the array.

What is the big-oh time for your entire task if you apply linear (sequential) search every time? Explain your answer.                                                                                    

Also explain whether you used any kind of sorting technique to presort the array before performing the searches.

Explanation / Answer

Q. Explain why merge sort always achieves O(nlog n) runtime complexity.It cannot be O(n).

Ans. In merge sort, the input is divided in 2 halves, recursively continues it for a limit and then at the end sorts the divided halves and merges back to get the sorted result.

As it always divides the input in half each level recursively, the recurrence relation is given by

T(n/2) [reducing to half] X T(n) [merge n items in end]

This time complexity is same for all cases (worst, average and best) as merge sort always slices the input and in the end merge linearly.

Q. Time complexity of following scenarios:

1. Insertion sort applied on an array where all values are equal.

Ans. In this case the items in array are already sorted. Here there won’t be any sliding to right or left and hence we will the process in O(n) time.

2. Bubble sort applied on an array where items are already in sorted order.

Ans. Bubble sort is swapping sort where, each element is sorted in nested manner at each iteration.

In case the array is already sorted then it would take O(n) times.

3. Suppose you have an array A = {8, 5, 6, 3}. Your job is to sort elements of A in increasing order. Suppose a comparison instruction takes 2 nanoseconds and an exchange (swap) instruction takes 10 nanoseconds. Design a scheme that uses minimum amount of time to achieve the sorted order. Indicate the time in nanoseconds as well. (Show your work or explain how you achieve your minimum time)

Ans. One of the popular comparison sort is Heapsort, it uses binary search tree to create heap which can be used to sort the input items. It pretty much work like insertion sort where we find the max element and then pushes that to the end. The total running time is O(nlogn)[ to create heap at each level -log(n) and extract n elements at each level -n]

4. Suppose you have an unsorted array of n distinct elements. You are required to perform n searches on the array. What is the big-oh time for your entire task if you apply linear (sequential) search every time? Explain your answer.

Ans. If we deploy the linear search then we will be scanning one item at a time without any shortcut. In this case, Time complexity would be O(n). In this case our run time will grow linearly along with the data size.

Binary Search:

One way of optimization is cutting down the input in half based on the value of to be searched item and determining which half of the cut will be having our item, and recursively carry out this process. But one major prerequisites of this method are that the input must be sorted at the beginning.

The time complexity of binary search would be O(logn)[similar to the merge sort division]

Practically we would not get presort array, then we have to use or sorting technique before searching.

A well implemented counting sorting would take O(n) time. Now on top of that we would apply binary search. So total run time would be in O(nlogn) range.

Related Questions

Navigate

• Browse (All)
• Browse E
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.