## Merge-Sort

 Question 1
Assume that a mergesort 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?
 A 256 B 512 C 1024 D 2048
Algorithms       Merge-Sort       GATE 2015(Set-03)
Question 1 Explanation:
Time complexity of merge sort = O(n log n) = an log n
where c is some constant
It is given that for n = 64,
cn log n = 30
c × 64 log 64 = 30
c × 64 × 6 = 30
c = 5/64
Now, the value of n for
c n log n = 360
5/64 × n log n = 360
n log n = 360×64/5
= 72 × 64 = 29 × 9
So for n = 29, it satisfies.
So, n = 29 = 512
 Question 2
A list of n strings, each of length n, is sorted into lexicographic order using the merge-sort algorithm. The worst case running time of this computation is
 A O (n log n) B O (n2 log n) C O (n2 + log n) D O (n2)
Algorithms        Merge-Sort       Gate 2012
Question 2 Explanation:
1.The comparison is strictly follow the Dictionary based order.
2.The length of the string is n, the time taken is to be O(n) for each comparison.
3. For level -1(bottom-up order): Every element has to be compared with other element the number of comparisons is O(n/2).
4. For level -1(bottom-up order): Total time taken by one level is O(n2).
5. For copying level to level the time taken by O(n2).
So, For level -1= O(n2)+ O(n2)
6. Second level O(n2)+ O(n2).
;
;
;
Final n level (logn)*O(n2) = O(n2 logn)
There are 2 questions to complete.