1
GATE CSE 2016 Set 2
Numerical
+2
-0
The given diagram shows the flowchart for a recursive function $$A(n).$$ Assume that all statements, except for the recursive calls, have $$O(1)$$ time complexity. If the worst case time complexity of this function is $$O\left( {{n^\alpha }} \right),$$ then the least possible value (accurate up to two decimal positions) of $$\alpha$$ is ____________ .
2
GATE CSE 2015 Set 1
+2
-0.6
An algorithm performs $${\left( {\log N} \right)^{1/2}}$$ find operations, N insert operations, $${\left( {\log N} \right)^{1/2}}$$ delete operations, and $${\left( {\log N} \right)^{1/2}}$$decrease-key operations on a set of data items with keys drawn from a linearly ordered set. For a delete operation, a pointer is provided to the record that must be deleted. For the decrease-key operation, a pointer is provided to the record that has its key decreased. Which one of the following data structures is the most suited for the algorithm to use, if the goal is to achieve the best total asymptotic complexity considering all the operations?
A
Unsorted array
B
Min-heap
C
Sorted array
D
3
GATE CSE 2015 Set 1
+2
-0.6
Consider the following C function.
int fun1 (int n) {
int i, j, k, p, q = 0;
for (i = 1; i < n; ++i)
{
p = 0;
for (j = n; j > 1; j = j/2)
++p;
for (k = 1; k < p; k = k * 2)
++q;
}
return q;
}
Which one of the following most closely approximates the return value of the function fun1?
A
$$n^3$$
B
$$n{\left( {\log n} \right)^2}$$
C
$$n\log n$$
D
$$n\log \left( {\log n} \right)$$
4
GATE CSE 2015 Set 3
+2
-0.6
Let $$f\left( n \right) = n$$ and $$g\left( n \right) = {n^{\left( {1 + \sin \,\,n} \right)}},$$ where $$n$$ is a positive integer. Which of the following statements is/are correct?

\eqalign{ & \,\,\,\,\,\,\,{\rm I}.\,\,\,\,\,\,\,f\left( n \right) = O\left( {g\left( n \right)} \right) \cr & \,\,\,\,\,{\rm I}{\rm I}.\,\,\,\,\,\,\,f\left( n \right) = \Omega \left( {g\left( n \right)} \right) \cr}

A
Only $${\rm I}$$
B
Only $${\rm I}$$$${\rm I}$$
C
both $${\rm I}$$ and $${\rm I}$$$${\rm I}$$
D
Neither $${\rm I}$$ nor $${\rm I}$$$${\rm I}$$
GATE CSE Subjects
EXAM MAP
Medical
NEET