805 views

Is the answer to this solution is O( n2 log (n) ) or O( n log (n) )

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(n2) in order to compare

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

now ,we have to copy all of the elements in the next level which require = O(n2)

therefore, time taken for comparing + time taken to copy all the element  = so total time taken in one level  = O(n2) + O(n2) = O(n2)

therefore , for every level : O(n2) work is done .

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

and each level require : O(n2)

therefore , total work done = O( n2 log(n) )

by

NICE EXPLANATION

@Magma, keep it up

thanks a lot!

1 vote