Arjun Suresh (talk | contribs) (Created page with "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) '''...") |
Arjun Suresh (talk | contribs) |
||
| Line 1: | Line 1: | ||
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) | 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)''' | + | '''(A) $O(nloglogn)$''' |
| − | (B)$\ | + | (B)$ \Theta(nlogn)$ |
| − | (C) $\ | + | (C) $\Omega(nlogn)$ |
(D) $(n^{\frac{3}{2})$ | (D) $(n^{\frac{3}{2})$ | ||
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})$
Average Instruction execution time = Average CPU execution time + Average memory access time for each instruction = Average CPU execution time + Average address translation time + Average memory fetch for each instruction + Average page fault time for each instruction = 100 + ((0.9 * 0) + 0.1 * (2 * 150)) + 2*150 + (1/10000) * 8 * 1000 [ TLB access time assumed as 0 and 2 page tables needs to be accessed in case of TLB miss as the system uses two-level paging] = 100 + 30 + 300 + 800 = 1230 ns
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})$
Average Instruction execution time = Average CPU execution time + Average memory access time for each instruction = Average CPU execution time + Average address translation time + Average memory fetch for each instruction + Average page fault time for each instruction = 100 + ((0.9 * 0) + 0.1 * (2 * 150)) + 2*150 + (1/10000) * 8 * 1000 [ TLB access time assumed as 0 and 2 page tables needs to be accessed in case of TLB miss as the system uses two-level paging] = 100 + 30 + 300 + 800 = 1230 ns
GATECSE