Question

Write down the best case, worst case and average case complexity for merge sort.

Answer 1

Answer:

i dont know12467907415373794258031

Answer 2

Answer:

Time complexity of Merge Sort is O(n*Log n) in all the 3 cases (worst, average and best) as merge sort always divides the array in two halves and takes linear time to merge two halves. It requires equal amount of additional space as the unsorted array.

Quick Sort Algorithm

Time Complexity:Best :- O(n log(n))

Time Complexity:Average:- O(n log(n))

Time Complexity:Worst:-O(n2)

Merge sort Algorithm

Time Complexity:Best :- O(n log(n))

Time Complexity:Average:- O(n log(n))

Time Complexity:Worst:-O(n log(n))

1.Merge sort(Average, Best, Worst) = O(n * logn)

Also, Merge sort is not inplace(uses more space than the size of the given array cause it uses an extra array to hold the new sorted array) but stable(does not shuffle the position of same elements i.e if 1 is at 5th position and another 1 is at 7th position, 5th position 1 will come before the other one in sorted array).

2. Quick sort:

Best = O(n * logn)

Average = O(n * logn)

Worst = O(n ^ 2), when the elements are already sorted in ascending or descending order.

3. Randomised quick sort(selecting pivot randomly): O(n ^ 2), for all three case(best, average and worst).

Quick sort is inplace but unstable.

Explanation: