1
GATE CSE 2002
+1
-0.3
The solution to the recurrence equation
T(2k) = 3 T(2k-1) + 1, T (1) = 1, is:
A
2k
B
(3k+1 - 1)/2
C
3 log 2K
D
2 log 3K
2
GATE CSE 2001
+1
-0.3
Randomized quicksort is an extension of quicksort where the pivot is chosen randomly. What is the worst case complexity of sorting n numbers using randomized quicksort?
A
O(n)
B
O(n Log n)
C
O(n2)
D
O(n!)
3
GATE CSE 2000
+1
-0.3
Let s be a sorted array of n integers. Let t(n) denote the time taken for the most efficient algorithm to determined if there are two elements with sum less than 1000 in s. which of the following statements is true?
A
t (n) is O(1)
B
n < t (n) < $$n\log _2^n$$
C
$$n\log _2^n$$ < t (n) < $$\left( {\matrix{ n \cr 2 \cr } } \right)$$
D
t(n) = $$\left( {\matrix{ n \cr 2 \cr } } \right)$$
4
GATE CSE 1999
+1
-0.3
A sorting technique is called stable if:
A
It takes O(nlog n)time
B
It maintains the relative order of occurrence of non-distinct elements
C
It uses divide and conquer paradigm
D
It takes O(n) space
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