retagged by
26,098 views
75 votes
75 votes

Suppose there are $\lceil \log n \rceil$ sorted lists of $\lfloor n /\log n \rfloor$ elements each. The time complexity of producing a sorted list of all these elements is: (Hint:Use a heap data structure)

  1. $O(n \log \log n)$
  2. $\Theta(n \log n)$
  3. $\Omega(n \log n)$
  4. $\Omega\left(n^{3/2}\right)$
retagged by

15 Answers

8 votes
8 votes
Number of  List = Log(n) , Number of elements in each list = n/Log(n)

Take the pair appraoch( like merge in pairs , (1,2) is first pair  , (3,4) is the second pair , (4,5) , (6,7)...... (log(n) - 1,logn) will be the log(n)/2 th pair and merge using merge procedure of mergesort which takes Theta(k) where k is the number of elements in big one list.

Thus for first attempt the work will be [ ( n/log(n) ) *  ( log(n)/2 ) ]= n/2  as theta(n/log(n)) work has to be done for each pair and total log(n)/2 pairs are there

Second attempt , as now we have ( log(n)/2 ) list so again make pairs but now element in each list is 2n/log(n)

thus work will be =>  ( 2n/logn) * (log(n)/4 )  = n/2

similliarly again number of list will be half then make pairs thus for third attempt work will

be  = (4n/logn) * (log(n)/8)  = n/2

and so on....

total log(logn) attempt will be there , after that we will get single list of n elements

Thus (n/2 + n/2 + n/2 + ....... log(logn) terms )

thus ans = (n/2)* ( log(logn) ) = n log(logn)
edited by
3 votes
3 votes

Please correct me if I am wrong.

  • See, if we use merge sort algorithm then it uses divide and conquer mechanism and divide the list into small parts and then merge them by using merge procedure.
  • Now in any level, there is n/logn elements in the array and we need to merge them. To merge two array of size n/2 merge procedure take O(n/2+n/2) = O(n) time.
  • So to merge two array of size n/logn it will take 2n/logn time.
  • Now total number of such pair will be number of array/2 =logn/2
  • so in each level total number of comparison/movement will be sum of comparison/movement of all the pairs.
  • Total number of pairs = logn/2
  • each pair take 2n/logn time to get merge.
  • So total time taken at each level will be (2n/logn)*logn/2 =n.
  • Now the depth of the tree formed by merge sort while dividing the problem into subproblem is equal to logm for m elements.
  • So for logn elements the depth of tree will be loglogn.
  • Now we merge each pair until it get merge till the root level of the tree so total loglogn level require and each level take time equals to n
  • So total time taken will be O(nloglogn)
1 votes
1 votes
Lets start with 2 list each of size n

to merge them we will need, O( n+n ) = O (2n)

similarly to merge k list of size n = O ( kn )

Now to merge log(n) lists of size n/log(n)

it will take   O ( log(n) * n / log(n)  ) = O ( n )
Answer:

Related questions