1
GATE CSE 2002
MCQ (Single Correct Answer)
+2
-0.6
The running time of the following algorithm Procedure A(n)
If n<=2 return (1) else return (A([$$\sqrt n $$])); is best described by
A
O(n)
B
O(log n)
C
O(log log n)
D
O(1)
2
GATE CSE 2002
MCQ (Single Correct Answer)
+2
-0.6
Consider the following algorithm for searching for a given number x in an unsorted array A[1..n] having n distinct values:
1. Choose an i uniformly at random fro 1..n;
2. If A[i]=x then stop else Goto 1;
Assuming that x is present A, what is the expected number of comparisons made by the algorithm before it terminates?
A
n
B
n-1
C
2n
D
n/2
3
GATE CSE 2000
MCQ (Single Correct Answer)
+2
-0.6
Consider the following functions
$$f(n) = 3{n^{\sqrt n }}$$
$$g(n) = {2^{\sqrt n {{\log }_2}n}}$$
$$h(n) = n!$$
Which of the following is true?
A
h(n) is O (f(n))
B
h(n) is O (g(n))
C
g(n) is not O (f(n))
D
f(n) is O (g(n))
4
GATE CSE 1994
MCQ (Single Correct Answer)
+2
-0.6
Conside the following two functions:
$${g_1}(n) = \left\{ {\matrix{ {{n^3}\,for\,0 \le n < 10,000} \cr {{n^2}\,for\,n \ge 10,000} \cr } } \right.$$
$${g_2}(n) = \left\{ {\matrix{ {n\,for\,0 \le n \le 100} \cr {{n^3}\,for\,n > 100} \cr } } \right.$$ Which of the following is true:
A
$${g_1}(n)\,is\,0\,({g_2}(n))$$
B
$${g_1}(n)\,is\,0\,({n^3})$$
C
$${g_2}(n)\,is\,0\,({g_1}(n))$$
D
$${g_2}(n)\,is\,0\,(n)$$
GATE CSE Subjects
Software Engineering
Web Technologies
EXAM MAP