3,699 views
2 votes
2 votes
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)?

2 Answers

6 votes
6 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. 

0 votes
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)

 

 

Related questions

2 votes
2 votes
1 answer
1
8 votes
8 votes
2 answers
2
4 votes
4 votes
2 answers
4
Shreya Kapoor asked Jun 16, 2016
8,365 views
$k$ sorted arrays, each with $n$ elements, you want to combine those arrays into a single sorted array of $kn$ elements. Time Complexity?a.$O(kn)$b.$O(knlogk)$ c.$O(nk^{...