GATE2005 q39 - Revision history

Arjun Suresh: /* {{Template:Author|Arjun Suresh|{{arjunweb}} }} */

2015-09-06T14:29:52Z

‎{{Template:Author|Arjun Suresh|{{arjunweb}} }}

Arjun Suresh: /* {{Template:Author|Arjun Suresh|{{arjunweb}} }} */

2015-09-06T14:27:03Z

‎{{Template:Author|Arjun Suresh|{{arjunweb}} }}

Arjun Suresh at 14:25, 6 September 2015

2015-09-06T14:25:44Z

Arjun Suresh: /* {{Template:Author|Arjun Suresh|{{arjunweb}} }} */

2015-09-06T14:20:04Z

‎{{Template:Author|Arjun Suresh|{{arjunweb}} }}

Arjun Suresh at 15:19, 30 July 2014

2014-07-30T15:19:23Z

Arjun Suresh at 11:29, 15 July 2014

2014-07-15T11:29:11Z

Arjun Suresh at 11:16, 15 July 2014

2014-07-15T11:16:57Z

Arjun Suresh at 11:16, 15 July 2014

2014-07-15T11:16:50Z

Arjun Suresh at 11:16, 15 July 2014

2014-07-15T11:16:40Z

Arjun Suresh at 11:16, 15 July 2014

2014-07-15T11:16:18Z

← Older revision		Revision as of 14:29, 6 September 2015
Line 11:		Line 11:

	==={{Template:Author\|Arjun Suresh\|{{arjunweb}} }}===		==={{Template:Author\|Arjun Suresh\|{{arjunweb}} }}===
−	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 in heap is $O(\log n)$ ~~and inserting an element on a heap of size $n$ is~~ $~~O(\log~~ n)$. (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)$.	+	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)$.

← Older revision		Revision as of 14:27, 6 September 2015
Line 11:		Line 11:

	==={{Template:Author\|Arjun Suresh\|{{arjunweb}} }}===		==={{Template:Author\|Arjun Suresh\|{{arjunweb}} }}===
−	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 $~~\Theta~~(\log\log n)$ time as delete in heap is $~~\Theta~~(\log n)$ and inserting an element on a heap of size $n$ is $~~\Theta~~(\log n)$. (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)$.	+	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 in heap is $O(\log n)$ and inserting an element on a heap of size $n$ is $O(\log n)$. (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)$.

← Older revision		Revision as of 14:25, 6 September 2015
Line 7:		Line 7:
	(C) $\Omega(n\log n)$		(C) $\Omega(n\log n)$

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

← Older revision		Revision as of 14:20, 6 September 2015
Line 11:		Line 11:

	==={{Template:Author\|Arjun Suresh\|{{arjunweb}} }}===		==={{Template:Author\|Arjun Suresh\|{{arjunweb}} }}===
−	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 in heap is $O(1)$ and inserting an element on a heap of size $n$ is $O(\log n)$. (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)$.	+	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 $\Theta(\log\log n)$ time as delete in heap is $\Theta(\log n)$ and inserting an element on a heap of size $n$ is $\Theta(\log n)$. (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)$.

← Older revision		Revision as of 15:19, 30 July 2014
Line 11:		Line 11:

	==={{Template:Author\|Arjun Suresh\|{{arjunweb}} }}===		==={{Template:Author\|Arjun Suresh\|{{arjunweb}} }}===
−	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 ~~came in~~ 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 in heap is $O(1)$ and inserting an element on a heap of size $n$ is $O(\log n)$. (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)$.	+	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 in heap is $O(1)$ and inserting an element on a heap of size $n$ is $O(\log n)$. (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)$.

← Older revision		Revision as of 11:29, 15 July 2014
Line 18:		Line 18:
	[[Category:Algorithms & Data Structures Questions from GATE]]		[[Category:Algorithms & Data Structures Questions from GATE]]
	[[Category:GATE2005]]		[[Category:GATE2005]]
−	~~[[Category:Algorithms questions]]~~

← Older revision		Revision as of 11:16, 15 July 2014
Line 1:		Line 1:
−	Suppose there are $\~~logn~~$ 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)	+	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)$'''		'''(A) $O(n\log \log n)$'''

@@ Line 1: / Line 1: @@
 Suppose there are $\logn$ 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 \logn)$'''
+'''(A) $O(n\log \log n)$'''
 (B) $ \Theta(n\log n)$

@@ Line 1: / Line 1: @@
 Suppose there are $\logn$ 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\logn)$'''
+'''(A) $O(n\log \logn)$'''
-(B) $ \Theta(n\logn)$
+(B) $ \Theta(n\log n)$
-(C) $\Omega(n\logn)$
+(C) $\Omega(n\log n)$
 (D) $(n^{\frac{3}{2}})$

@@ Line 1: / Line 1: @@
-Suppose there are $logn$ 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)
+Suppose there are $\logn$ 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\logn)$'''
-(B) $ \Theta(nlogn)$
+(B) $ \Theta(n\logn)$
-(C) $\Omega(nlogn)$
+(C) $\Omega(n\logn)$
 (D) $(n^{\frac{3}{2}})$
@@ Line 11: / Line 11: @@
 ==={{Template:Author|Arjun Suresh|{{arjunweb}} }}===
-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 came in 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(loglog n)$ time as delete in heap is $O(1)$ and inserting an element on a heap of size $n$ is $O(log n)$. (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 loglog n)$.
+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 came in 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 in heap is $O(1)$ and inserting an element on a heap of size $n$ is $O(\log n)$. (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)$.