Dark Mode

805 views

6 votes

Best answer

here , In order to sort the strings we are follow lexicographically order / Dictionary Order ,

ie: if i have two strings aab and aaa, how to compare them is ist we have to compare the ist letter of the string which is (a and a) they are same ,

then 2nd letter a and a they are same , then compare 3rd letter from strings which is a and b .

therefore aaa is lesser then aab , therefore this "aaa" has to come in the beginning ,

so that is the comparison has to be done .

Now if the ist string is having "n " length and the 2nd string having "n" length

then , how much time will it take to compare is = actually we do characters wise comparing

therefore , for one comparison the Time complexity = O(n)

Now , there are "n" Strings and the size of each String is "n" .

Now , As we do 2-way merging , we take 2 strings and compare them and merge the 2 elements into a lexicographically order

therefore , no of comparison are going to be = O$(\frac{n}{2})$ = O(n)

and every comparison is going to take : O(n)

therefore , it's going to take : O(n^{2}) in order to compare

As we know total size of the list = (each string have "n" characters) * ( total "n" strings are there ) = n^{2}

now ,we have to copy all of the elements in the next level which require = O(n^{2})

therefore, time taken for comparing + time taken to copy all the element = so total time taken in one level = O(n^{2}) + O(n^{2}) = O(n^{2})

therefore , for every level : O(n^{2}) work is done .

then number of levels are there = O( log (n) ) levels

and each level require : O(n^{2})

therefore , total work done = O( n^{2 }log(n) )