Merge Sort

Question

A list of n string, each of length n, is sorted into lexicographic order using the merge-sort algorithm. The worst case running time of this computation is

(A) (B) (C) (D)

Answer 1

you know that for sorting n elements it take n.log(n) time

why this is happened ?

due to element comparission take constant time. ( at each level )

 

but here element comparission takes O(n) times ====> time complexity of required question = O(n² log n)

Comments

Sir, please explain why comparison in lexicographical order is taken O(n) times rather than O(1).

---

if it is integer, comparssions take O(1) ---------- due to a < b or b < a or a=b

if it is string with length 'n' , then comparission takes O(n) ------- due to you have to compare each letter in the strings in the worst case

ex:- "ABC", "ABD", how these two strings compared ( string length=3, in worst case it requires 3 comparissions )?

A == A, Proceed Further

B == B, Proceed Further

C ==D, not equal ===> as per lexograhical order, C < D ===> "ABC" < "ABD"

Answer 2

In lexicographical order you don't need to sort a string. You have to compare strings and sort lists as dictionary. To compare 2 strings(size=n) It will take O(n).

To sort n lists merge sort take O(nlogn).

So finally n*nlogn = O(n^2logn).

Answer 3

n = length of string

i = n

Step X :pick the i’^th character of each string and sort all the string on the basis of the i’^th character

this took O(nlogn) time

i = i – 1

repeat step X

Doing this for n times makes the complexity = O(n^2 logn)

 

Reason this worked: Merge sort is a stable sort

 

Ans: B