Quiz on sorting

#1

can anyone explain me these two questions??

1.Assume that a merge sort algorithm in the worst case takes 30 seconds for an input of size 64. Which of the following most closely approximates the maximum input size of a problem that can be solved in 6 minutes?

2.Which of the following changes to typical QuickSort improves its performance on average and are generally done in practice?

  1. Randomly picking up to make worst case less likely to occur.
  2. Calling insertion sort for small sized arrays to reduce recursive calls.
  3. QuickSort is tail recursive, so tail call optimizations can be done.
  4. A linear time median searching algorithm is used to pick the median, so that the worst case time reduces to O(n Log n)

just not getting these two question

#2

For your first doubt:
Time complexity of merge sort is Θ(nLogn)

c64Log64 is 30
c64*6 is 30
c is 5/64

For time 6 minutes

5/64nLogn = 660

nLogn = 72*64 = 512 * 9

n = 512.

For your second doubt:
The 4th optimization is generally not used, it reduces the worst case time complexity to O(nLogn), but the hidden constants are very high.

Hope it helped you :grinning:

#3

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.