GATE CS previous year questions · 4 questions
Consider the following recurrence relation:
\(T(n) = 2T(n - 1) + n2^{n}\) for \(n \gt 0\), \(T(0) = 1\).
Which ONE of the following options is CORRECT?
Answer: (A)
Divide both sides by \(2^{n}\) and put \(S(n) = T(n)/2^{n}\). The recurrence becomes \(S(n) = S(n - 1) + n\) with \(S(0) = 1\).
So \(S(n) = 1 + (1 + 2 + \dots + n) = 1 + \frac{n(n+1)}{2}\), and \(T(n) = 2^{n}\left(1 + \frac{n(n+1)}{2}\right) = \Theta(n^{2}2^{n})\).
Answer: A
A meld operation on two instances of a data structure combines them into one single instance of the same data structure. Consider the following data structures:
P: Unsorted doubly linked list with pointers to the head node and tail node of the list.
Q: Min-heap implemented using an array.
R: Binary Search Tree.
Which ONE of the following options gives the worst-case time complexities for meld operation on instances of size \(n\) of these data structures?
Answer: (A)
Answer: A
Given an integer array of size \(N\), we want to check if the array is sorted (in either ascending or descending order). An algorithm solves this problem by making a single pass through the array and comparing each element of the array only with its adjacent elements. The worst-case time complexity of this algorithm is
Answer: (A)
The algorithm walks once through the array, comparing each adjacent pair \((a_{i}, a_{i+1})\), and stops as soon as a pair breaks the order. The worst case is an array that really is sorted (or breaks the order only at the very end): all \(N-1\) pairs must then be compared before the algorithm can answer.
So the worst-case time grows linearly with \(N\). It is \(\Theta(N)\), which means it is both \(O(N)\) and \(\Omega(N)\).
B fails because no method can do better: an element that is never examined could break the order, so the time is also \(\Omega(N)\). C and D fail because a single pass is \(O(N)\).
Answer: A
Consider the following recurrence relation:
\[T(n) = \begin{cases} \sqrt{n}\,T\left(\sqrt{n}\right) + n & \text{for } n \ge 1, \\ 1 & \text{for } n = 1. \end{cases}\]
Which one of the following options is CORRECT?
Answer: (A)
Divide both sides by \(n\): \(\frac{T(n)}{n} = \frac{T(\sqrt{n})}{\sqrt{n}} + 1\). Writing \(S(n) = T(n)/n\), this is \(S(n) = S(\sqrt{n}) + 1\): each step takes a square root and adds 1.
For \(n = 2^{2^{k}}\), taking the square root \(k\) times brings \(n\) down to a constant, so \(S(n) = \Theta(k) = \Theta(\log \log n)\) and \(T(n) = n\,S(n) = \Theta(n \log \log n)\).
In the recursion tree, every level does exactly \(n\) work in total (for example \(\sqrt{n}\) subproblems of size \(\sqrt{n}\) cost \(\sqrt{n} \cdot \sqrt{n}\)), and there are \(\log \log n\) levels.
Answer: A