sorted list

Question

we are given (log m) sorted list each of size (log n) / (log m) the time complexity of merging list into single sorted list using mergesort is equal to 

a) O ( log m log(log n) )

​​​​​​​b) O ( log n log(log m) )

​​​​​​​c) O ( log m log n)

​​​​​​​d) O ( m log log n)

Answer 1

we have logm list of size  logn/logm---

so in each step we have to merge two list and in each step all the comparisons will take ((logm X logn)/logm)= logn time

and we have to do merging till k th step in which 2^k= logm (2^k beause in each step we are merging two list)

                                                                     k= log(log m)    

                                                        so

                                   Logn + log n + log n ...... for log(logm) times

                                    so complexity should be logn log(logm)

so answer should be B

Comments

i think this question is incomplete

here can be three case

first if i merge at a time

second merge one one people at a time .

third merge two two people at a time.

here you are considering third case why?

am i right?