({{Template:Author|Arjun Suresh|{{arjunweb}} }})
 
(20 intermediate revisions by the same user not shown)
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 $\log n$ sorted lists of $\frac{n}{\log n}$ 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(n\log \log n)$'''
 
   
 
   
(B)$ \Theta(nlogn)$
+
(B) $ \Theta(n\log n)$
 
   
 
   
(C) $\Omega(nlogn)$
+
(C) $\Omega(n\log n)$
 
   
 
   
(D) $(n^{\frac{3}{2})$
+
(D) $\Omega(n^{\frac{3}{2}})$
 
   
 
   
  
 
==={{Template:Author|Arjun Suresh|{{arjunweb}} }}===
 
==={{Template:Author|Arjun Suresh|{{arjunweb}} }}===
Average Instruction execution time
+
Since we have $\log n$ lists we can make a min-heap of $\log n$ elements by taking the first element from each of the $\log n$ 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 was added to the heap. (This identity can be done by making a structure of two values, one for the number and one for identifying the origin sorted list of that number and storing this structure in the heap). In this way each delete and the corresponding insert will take $O(\log\log n)$ time as delete and insert operations in heap is $O(\log n)$ for $n$ elements (here, heap size is $\log n$). Now, we have a total of $\log n \times \frac{n}{\log n} = n$ elements. So, total time will be $O(n \log\log n)$.
= 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
 
  
  
Line 24: Line 18:
 
[[Category:Algorithms & Data Structures Questions from GATE]]
 
[[Category:Algorithms & Data Structures Questions from GATE]]
 
[[Category:GATE2005]]
 
[[Category:GATE2005]]
[[Category:Algorithms questions]]
 

Latest revision as of 14:29, 6 September 2015

Suppose there are $\log n$ sorted lists of $\frac{n}{\log n}$ elements each. The time complexity of producing a sorted list of all these elements is: (Hint:Use a heap data structure)

(A) $O(n\log \log n)$

(B) $ \Theta(n\log n)$

(C) $\Omega(n\log n)$

(D) $\Omega(n^{\frac{3}{2}})$


Solution by Arjun Suresh

Since we have $\log n$ lists we can make a min-heap of $\log n$ elements by taking the first element from each of the $\log n$ 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 was added to the heap. (This identity can be done by making a structure of two values, one for the number and one for identifying the origin sorted list of that number and storing this structure in the heap). In this way each delete and the corresponding insert will take $O(\log\log n)$ time as delete and insert operations in heap is $O(\log n)$ for $n$ elements (here, heap size is $\log n$). Now, we have a total of $\log n \times \frac{n}{\log n} = n$ elements. So, total time will be $O(n \log\log n)$.




blog comments powered by Disqus

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




blog comments powered by Disqus