1
GATE CSE 1994
+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)$$
2
GATE CSE 1993
+2
-0.6
$$\sum\limits_{1 \le k \le n} {O(n)}$$ where O(n) stands for order n is:
A
O(n)
B
O(n2)
C
O (m3)
D
O(3n2)
3
GATE CSE 1990
Subjective
+2
-0
Express T(n) in terms of the harmonic number Hn = $$\sum\limits_{t = 1}^n {1/i,n \ge 1}$$ where T(n) satisfies the recurrence relation, T(n) = $${{n + 1} \over 2}$$ T(n-1) + 1, for $$n \ge 2$$ and T(1) = 1 What is the the asymptotic behavior of T(n) as a function of n?
4
GATE CSE 1987
Subjective
+2
-0
Solve the recurrence equations
T (n) = T (n - 1) + n
T (1) = 1
GATE CSE Subjects
Theory of Computation
Operating Systems
Algorithms
Digital Logic
Database Management System
Data Structures
Computer Networks
Software Engineering
Compiler Design
Web Technologies
General Aptitude
Discrete Mathematics
Programming Languages
Computer Organization
EXAM MAP
Joint Entrance Examination