GATE CSE 2005 | Question: 39

Question

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)

• A. $O(n \log \log n)$
• B. $\Theta(n \log n)$
• C. $\Omega(n \log n)$
• D. $\Omega\left(n^{3/2}\right)$

Comments

Refer this for better understanding of question.

http://www.geeksforgeeks.org/merge-k-sorted-arrays/

---

plzz correct the question.  size of each sorted list is n/logn..?

---

The merge is two-way merge.

---

https://gateoverflow.in/16103/the-time-complexity-of-producing-a-sorted-list

---

https://gateoverflow.in/51068/merge-sort

---

what is this ??

---

How can u take " n -nlog(logn)/logn , here we can take as nlog(logn)/logn "???

and this should not be the logic...

Anyone verify this..

---

Try to solve the following problem -
https://www.interviewbit.com/problems/merge-two-sorted-lists-ii/

---

Question say use heap data structure why people are using k way merge sort??

---

Answer: A

---

The k-way merge problem consists of merging k sorted arrays to produce a single sorted array with the same elements. Denote by n the total number of elements. n is equal to the size of the output array and the sum of the sizes of the k input arrays. For simplicity, we assume that none of the input arrays is empty. As a consequence , which simplifies the reported running times. The problem can be solved in running time with  space. Several algorithms that achieve this running time exist.

Using Heap: The idea is to maintain a min-heap of the k lists, each keyed by their smallest current element. A simple algorithm builds an output buffer with nodes from the heap. Start by building a min-heap of nodes, where each node consists of a head element of the list, and the rest (or tail) of the list. Because the lists are sorted initially, the head is the smallest element of each list; the heap property guarantees that the root contains the minimum element overall lists. Extract the root node from the heap, add the head element to the output buffer, create a new node out of the tail, and insert it into the heap. Repeat until there is only one node left in the heap, at which point just append that remaining list (head and tail) to the output buffer.

Source: https://en.wikipedia.org/wiki/K-way_merge_algorithm#Direct_k-way_merge

---

Adding @madhes23

Rather k-way merge that uses heap runs in O(nlogk), but direct k way merge is not optimized which runs in O(nk)

From wiki:

Direct k-way merge

In this case, we would simultaneously merge k-runs together.

A straightforward implementation would scan all k arrays to determine the minimum. This straightforward implementation results in a running time of Θ(kn). Note that this is mentioned only as a possibility, for the sake of discussion. Although it would work, it is not efficient.

We can improve upon this by computing the smallest element faster. By using either heaps, tournament trees, or splay trees, the smallest element can be determined in O(log k) time. The resulting running times are therefore in O(n log k).

Source – https://en.wikipedia.org/wiki/K-way_merge_algorithm#Direct_k-way_merge

---

@mohan123 what does the meaning of each level cost?

---

@mohan123 thank you so much man your solution helped me a lot 

 

---

Why most answers based on merge procedure? We have to use heap.

---

Does no. of list = ceil(logn) and each of size = floor(n/logn). Does ceil and floor makes any difference?

---

Using Heap:

• Number of lists k=⌈log⁡n⌉

• Make a min-heap of size k containing the current smallest element from each list.

• Each extract-min and subsequent insert costs O(logk)=O(loglogn).

• You perform one extract/insert per element; there are n elements total.

• Total time =n⋅O(loglogn)=O(nloglogn).

 

Using pair-wise merge:

• There are logn arrays, let k=logn and let size of each array be x
• Cost of merging two arrays is 2x (approx.) and we did it pair-wise, so for k/2 pairs the cost is k/2 * 2x = kx
• Now 1st level has k arrays then 2nd level has k/2 arrays then 3rd level has k/4 arrays, so total logk levels and each level has cost of kx
• Final cost = logk * kx = loglogn * (logn * n/logn) = nloglogn

---

Understand with example:

suppose n=1024  then ⌈log⁡n⌉ = 10 (10 sorted lists)

each of size ⌈n/log⁡n⌉=⌈1024/10⌉=103

put the first(i.e smallest) element of each of the 10 lists into a min-heap (heap size k=10).

Repeat untill the output has all n element (i.e n=1024)

extract min element from the heap and append it to output.

important: if the extracted element came from list i and list i still has element, insert the next element from

 list i into  the heap.

Now count the operation:

total element n=1024

each element causes one extract and at most one insert, so Θ(n) heap operations.

heap size is k= ⌈log⁡n⌉, so each heap operation costs O(log⁡k)=O(log⁡log⁡n)

Total time complexity : Θ(n)⋅O(log⁡k) that  is O(nlog⁡log⁡n)

---

In Short, The heap has only log n elements, every heap operation takes log log n time, and we do this n times
so Time complexity in short is O(n log log n).

Answer 1

Since we have $\log n$ lists we can make a min-heap of $\log n$ elements by taking the first element from each of the $\log n$ sorted lists. Now, we start deleting the min-element from the heap and put the next element from the sorted list from which that element was added to the heap. (This identity can be done by making a structure of two values, one for the number and one for identifying the origin sorted list of that number and storing this structure in the heap). In this way each delete and the corresponding insert will take $O(\log\log n)$ time as delete in heap of size $n$ is $O(\log n)$ and inserting an element on a heap of size $n$ is also $O(\log n)$. (here, heap size is $\log n$). Now, we have a total of $\log n \times \frac{n}{\log n} = n$ elements. So, total time will be $O(n \log\log n)$.

Correct Answer: $A$

Comments

@Shaik Masthan sir

As maximum comments are referring for 2-way merge sort even though question specifically mentioned for $heap.$ Here in this case both the approaches are giving same answer.

My question--if there is a change in the question in the # of sorted list and # of elements in each sorted list. Does both the approaches still gives the same answer. As making use of 2-way MS is easy compared to think in terms of heap. Please help me out.

---

@MRINMOY_HALDER, According to your second approach time complexity is greater than when heap is used.

In approach 2,

You are not finding time complexity you are finding total number of elements..

2- way merge sort will merge 2 lists each from logn lists in level 1,

in level 2:: we have logn/2 lists with each list of size 2*(n/logn)...

in level 3:: we have (logn/$2^{2}$) lists with size 4*(n/logn)

.... so on till level k when there will be 1 single list..

in level k we have (logn/$2^{k}$) lists with size $2^{k}$*(n/logn)therefore,

logn/$2^{k}$=1 

logn= $2^{k}$ and k= loglogn..(Total Passes/Height of the tree)

Cost at each level/No of elements=n.

Hence T.C= cost at each level * height= O(n*loglogn).. 

So, according to me merge sort gives same result. Please tell me if I'm wrong.

 

 

---

@pranavsettaluri9 I also think about 2-way-merge sort.

Answer 2

We can merge x arrays of each size y in in O(xy*Logy) time using Min Heap.

x = n/Logn
y = Logn

We get O(n/Logn * Logn * Log Log n) which is O(nLogLogn)

Comments

in question , number of elements in each lis is n/logn

so y = n/logn

---

0(xy*logx ) will satisfy because we can merge x arrays of each size y in0(xy*logx)..

Answer 3

Using Min Heap hope it can help...

Answer 4

This may help!!!

Answer 5

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)

Answer 6

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)

Comments

Perfectly written man, went straight into my head. Respect !!

---

Honestly this is also the first thing I did...Worst clue ever given