Arjun Suresh (talk | contribs) |
Arjun Suresh (talk | contribs) |
||
| Line 3: | Line 3: | ||
'''(A) $O(nloglogn)$''' | '''(A) $O(nloglogn)$''' | ||
| − | (B)$ \Theta(nlogn)$ | + | (B) $ \Theta(nlogn)$ |
(C) $\Omega(nlogn)$ | (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