1
GATE CSE 2022
MCQ (More than One Correct Answer)
+1
-0.33
Consider the following recurrence:
f(1) = 1;
f(2n) = 2f(n) $$-$$ 1, for n $$\ge$$ 1;
f(2n + 1) = 2f(n) + 1, for n $$\ge$$ 1;
Then, which of the following statements is/are TRUE?
2
GATE CSE 2020
MCQ (Single Correct Answer)
+1
-0.33
For parameters a and b, both of which are $$\omega \left( 1 \right)$$,
T(n) = $$T\left( {{n^{1/a}}} \right) + 1$$, and T(b) = 1.
Then T(n) is
T(n) = $$T\left( {{n^{1/a}}} \right) + 1$$, and T(b) = 1.
Then T(n) is
3
GATE CSE 2015 Set 3
MCQ (Single Correct Answer)
+1
-0.3
Consider the equality $$\sum\limits_{i = 0}^n {{i^3}} = X$$ and the following choices for $$X$$
$$\eqalign{ & \,\,\,\,\,\,\,{\rm I}.\,\,\,\,\,\,\Theta \left( {{n^4}} \right) \cr & \,\,\,\,\,{\rm I}{\rm I}.\,\,\,\,\,\,\Theta \left( {{n^5}} \right) \cr & \,\,\,{\rm I}{\rm I}{\rm I}.\,\,\,\,\,\,O\left( {{n^5}} \right) \cr & \,\,\,{\rm I}V.\,\,\,\,\,\,\Omega \left( {{n^3}} \right) \cr} $$
The equality above remains correct if $$𝑋$$ is replaced by
$$\eqalign{ & \,\,\,\,\,\,\,{\rm I}.\,\,\,\,\,\,\Theta \left( {{n^4}} \right) \cr & \,\,\,\,\,{\rm I}{\rm I}.\,\,\,\,\,\,\Theta \left( {{n^5}} \right) \cr & \,\,\,{\rm I}{\rm I}{\rm I}.\,\,\,\,\,\,O\left( {{n^5}} \right) \cr & \,\,\,{\rm I}V.\,\,\,\,\,\,\Omega \left( {{n^3}} \right) \cr} $$
The equality above remains correct if $$𝑋$$ is replaced by
4
GATE CSE 2013
MCQ (Single Correct Answer)
+1
-0.3
Which of the following is the tightest upper bound that represents the number of swaps required to sort n numbers using selection sort?
Questions Asked from Complexity Analysis and Asymptotic Notations (Marks 1)
Number in Brackets after Paper Indicates No. of Questions
GATE CSE Subjects
Theory of Computation
Operating Systems
Algorithms
Database Management System
Data Structures
Computer Networks
Software Engineering
Compiler Design
Web Technologies
General Aptitude
Discrete Mathematics
Programming Languages