View source for GATE2005 q39 ← GATE2005 q39

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})$

Solution by Arjun Suresh[edit]

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