Arjun Suresh (talk | contribs) |
Arjun Suresh (talk | contribs) |
||
| Line 1: | Line 1: | ||
| − | Suppose there are $logn$ sorted lists of $n | + | Suppose there are $logn$ sorted lists of $\frac{{n}{logn}}$ elements each. The time complexity of producing a sorted list of all these elements is: (Hint:Use a heap data structure) |
'''(A) $O(nloglogn)$''' | '''(A) $O(nloglogn)$''' | ||
| Line 11: | Line 11: | ||
==={{Template:Author|Arjun Suresh|{{arjunweb}} }}=== | ==={{Template:Author|Arjun Suresh|{{arjunweb}} }}=== | ||
| − | Since we have $logn$ lists we can make a min-heap of $logn$ elements by taking the first element from each of the $logn$ 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 came. (This identity can be done by making a structure of two values, one for the number and one for the origin sorted list and storing this structure in the heap). In this way each delete and the corresponding insert will take $O(loglogn)$ time as delete in heap is $O(1)$ and inserting an element on a heap of size $n$ is $O(nlogn)$. Now, we have a total of $logn \times n | + | Since we have $logn$ lists we can make a min-heap of $logn$ elements by taking the first element from each of the $logn$ 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 came. (This identity can be done by making a structure of two values, one for the number and one for the origin sorted list and storing this structure in the heap). In this way each delete and the corresponding insert will take $O(loglogn)$ time as delete in heap is $O(1)$ and inserting an element on a heap of size $n$ is $O(nlogn)$. Now, we have a total of $logn \times \frac{{n}{logn}} = n$ elements. So, the total time will be $O(n loglogn)$. |
Suppose there are $logn$ sorted lists of $\frac{{n}{logn}}$ elements each. The time complexity of producing a sorted list of all these elements is: (Hint:Use a heap data structure)
(A) $O(nloglogn)$
(B) $ \Theta(nlogn)$
(C) $\Omega(nlogn)$
(D) $(n^{\frac{3}{2}})$
Since we have $logn$ lists we can make a min-heap of $logn$ elements by taking the first element from each of the $logn$ 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 came. (This identity can be done by making a structure of two values, one for the number and one for the origin sorted list and storing this structure in the heap). In this way each delete and the corresponding insert will take $O(loglogn)$ time as delete in heap is $O(1)$ and inserting an element on a heap of size $n$ is $O(nlogn)$. Now, we have a total of $logn \times \frac{{n}{logn}} = n$ elements. So, the total time will be $O(n loglogn)$.
Suppose there are $logn$ sorted lists of $n/logn$ elements each. The time complexity of producing a sorted list of all these elements is: (Hint:Use a heap data structure)
(A) $O(nloglogn)$
(B) $ \Theta(nlogn)$
(C) $\Omega(nlogn)$
(D) $(n^{\frac{3}{2}})$
Since we have $logn$ lists we can make a min-heap of $logn$ elements by taking the first element from each of the $logn$ 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 came. (This identity can be done by making a structure of two values, one for the number and one for the origin sorted list and storing this structure in the heap). In this way each delete and the corresponding insert will take $O(loglogn)$ time as delete in heap is $O(1)$ and inserting an element on a heap of size $n$ is $O(nlogn)$. Now, we have a total of $logn \times n/logn = n$ elements. So, the total time will be $O(n loglogn)$.
GATECSE