The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+1 vote
1.3k views
Suppose there are $\log n$ sorted lists and each list contains $n/\log n$ elements. The time complexity of producing a sorted list of all these elements is (using merge algorithm)?
in Algorithms by Active (2.3k points) | 1.3k views

2 Answers

+2 votes

the answer is nloglogn . 

the time complexity will be height of tree * time taken to merge elements . so first of all find the height of tree. 
if n elements are given and 2 way merging is applied height is log n . 

take example 4 elemnts . now we merge 2 and merge 2. now on second last level there wll be 2 list of size 2 each  then there will be one only .like this as in pic 

so here log n list are there so height will be loglogn. and the complexity of merging wll depend on total number of element we have to copy to the next level . the number of element we have to copy are n/logn*logn which is n . so complexity is nloglogn. 

similar question n elments merge them using merge sort into one sorted list . 

similarly height is logn . and n elemnts i have to copy =nlogn. can solve anything. 

by Boss (15.8k points)
0
@Ravi How is no. of elements becoming 2? We are given log n lists, how are we splitting them?
0
they are not . i have just broken the problem to taking n elements in the sorted list for better understanding . so if we have n elements and then we have to merge them then at the second last level we will have pairs of 2-2 that what i mean. i have specified it also.
0

Okay. But then the algorithm is not clear to me. But I'm almost certain this complexity is not possible without using a heap. 

https://gateoverflow.in/784/gate2005_39

+1

@arjun sir it is possible with merging algorithm also.This is given in cormen second edition page number 38 as given below:

b) Show that sublists can be merged in theta(nlog(n/k)) worst case time.

but only difference is here n/k sorted sublist and each of lenth k but in our question logn sorted list and each of length n/logn and total number of elements in both the cases is n only

so we can say that time complexity=total number of elements * log (number of sublist)

=n * log(n/k)

that is why for this question n * log(logn)

(it is also true in simple case when we have array of n elemets then merge sort divide the array in such a whether until all array elememts split in to single single elements and then using merging algorithm we started merging by taking 2 elements at a time because single element is already sorted and here time complexity =theta(nlogn) that means time complexity =total number of elements * log (number of sublist)

here number of sublist is n because array is divided in such a whether until each list contain 1 element and then apply merging.)

therefore in this question we can also consider that our array is divided in such a whether until each list contain n/logn elements because these lists are sorted given in question then apply merging by taking 2 sorted list then we will get time complexity= 

total number of elements * log (number of sublist)

=n * log(logn)
 

0
Okay. Got it. Yes, that will work. But the procedure is not fully formal. It is like doing merge sort but stopping at a height when all sublists are sorted (not going toll 1).
0
This is answer cleared my doubts thanks....
0 votes

please tell someone what is wrong in this..

assume that there are k sorted files and each file contain n/k elements.To sort all these k files in to a single files we use merge algorithm that is first merge file1 and file 2 and later resultant file will be merged with third file continue this process until all files are merged.and we know that time taken for merging two sorted files of length m and n is O(m+n).

since we are merging two files of length n/k so it takes O(n/k+n/k)=O(2n/k)

merging resultant file with third file takes O(2n/k+n/k)=O(3n/k)

continue this process then total time complexity=

O(2n/k)+O(3n/k)+O(4n/k)+O(5n/k)+-------------------+O(kn/k)

=O(n/k)(2+3+4+5+6+----------------------+k)

=O(n/k)(k(k+1)/2)

=O(nk)

here k=logn

time complexity=O(nlogn)

 

 

by Active (2.3k points)
0

There is nothing wrong, but we can do better method. 

https://gateoverflow.in/784/gate2005_39

0
sir actually i want to know,same method (merge algo) used by @Ravi singh by taking 2, 2 list (they are calling it 2 way merge) but i also solving by taking 2 list at a time but i am going sequentially so what will be the name of my method , i can call it sequential merge
0
A name is not important. But I don't think that method by Ravi is correct. Because the no. of elements is not 2 at the end- it remains log n.
0
@arjun sir...but we r nt using the mergesort algorithm ,we r just using only merge algorithm so  i think we r not dividing it .it is already divided.....we will need some other method to recursively pass the array of sorted list to the merge algorithm again and again till we get the complete sorted list ...thats the reason u think it is incorrect right??
0
we have to sort logn sorted list which are already breakon. why are u trying to still break the problem, it is in it's native form. u have only merge .  and the question is saying merge algo not merge sort algorithm. and whether u understand my method or not, i was too a hell lot confussed but this was the  only method that work for me, and the method is not names as 2 way mergin i am joining 2 , 2 list at a time that why its two way .
what if is a three way merging. now we are going to join 3-3 so the height will be lognbase 3 . if we have n elements . here it will be n * log base 3logn. now u may understand that it also matters that whether it is a 2 way merging or 3 way or n way merging
0
@Ravi Yes, your method is correct and the secret is in picking the lists with smallest number of elements to merge first.

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
49,830 questions
54,807 answers
189,530 comments
80,840 users