GATE2005 q39 Revision as of 09:53, 24 June 2014 by Arjun Suresh (talk | contribs) (diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

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

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

Tweet