Crack
GATE
C
G
Topic
Asymptotic Analysis
Algorithms
0
/ 21 done
Questions per paper
All
MCQ
MSQ
NAT
2015 to 2026. Point at a year to read it.
0
1
2
3
2015
2019
2021
2023
2025
2026
Show as a table
Year
All
MCQ
MSQ
NAT
2015
2.7
2.3
0
0.3
2018
0
0
0
0
2019
1
1
0
0
2020
1
1
0
0
2021
1.5
1.5
0
0
2022
1
1
0
0
2023
2
0
2
0
2024
1
1
0
0
2025
0
0
0
0
2026
1.5
1
0.5
0
1
CS 2026 Set 2 · 1 mark · MCQ · Moderate
Consider the following functions, where
n
n
n
is a positive integer.
2
CS 2026 Set 2 · 1 mark · MSQ · Moderate
Which of the following can be recurrence relation(s) corresponding to an algorithm with time complexity
Θ
(
n
)
\Theta(n)
Θ
(
n
)
?
3
CS 2026 Set 2 · 2 marks · MCQ · Moderate
Consider an array
A
A
A
of integers of size
n
n
n
. The indices of
A
A
A
run from
1
1
1
to
n
n
n
. An algorithm is to be designed to check whether
A
A
A
satisfies the condition given below.
4
CS 2024 Set 1 · 1 mark · MCQ · Moderate
Given an integer array of size
N
N
N
, we want to check if the array is sorted (in either ascending or descending order). An algorithm solves this problem by making a single pass through the array and comparing each element of the array only with its adjacent elements. The worst-case time complexity of this algorithm is
5
CS 2024 Set 1 · 2 marks · MCQ · Hard
Consider the following recurrence relation:
6
CS 2023 · 1 mark · MSQ · Easy
Let
f
f
f
and
g
g
g
be functions of natural numbers given by
f
(
n
)
=
n
f(n)=n
f
(
n
)
=
n
and
g
(
n
)
=
n
2
g(n)=n^2
g
(
n
)
=
n
2
. Which of the following statements is/are TRUE?
7
CS 2023 · 2 marks · MSQ · Easy
Consider functions Function-1 and Function-2 expressed in pseudocode as follows:
8
CS 2022 · 1 mark · MCQ · Moderate
Which one of the following statements is TRUE for all positive functions
f
(
n
)
f(n)
f
(
n
)
?
9
CS 2021 Set 1 · 1 mark · MCQ · Moderate
Consider the following three functions.
10
CS 2021 Set 1 · 2 marks · MCQ · Moderate
Consider the following recurrence relation.
11
CS 2021 Set 2 · 2 marks · MCQ · Easy
For constants
a
≥
1
a \ge 1
a
≥
1
and
b
>
1
b > 1
b
>
1
, consider the following recurrence defined on the non-negative integers:
12
CS 2020 · 1 mark · MCQ · Hard
For parameters
a
a
a
and
b
b
b
, both of which are
ω
(
1
)
\omega(1)
ω
(
1
)
,
T
(
n
)
=
T
(
n
1
/
a
)
+
1
T(n) = T(n^{1/a}) + 1
T
(
n
)
=
T
(
n
1/
a
)
+
1
, and
T
(
b
)
=
1
T(b) = 1
T
(
b
)
=
1
. Then
T
(
n
)
T(n)
T
(
n
)
is
13
CS 2019 · 2 marks · MCQ · Moderate
There are
n
n
n
unsorted arrays:
A
1
,
A
2
,
…
,
A
n
A_1, A_2, \ldots, A_n
A
1
,
A
2
,
…
,
A
n
. Assume that
n
n
n
is odd. Each of
A
1
,
A
2
,
…
,
A
n
A_1, A_2, \ldots, A_n
A
1
,
A
2
,
…
,
A
n
contains
n
n
n
distinct elements. There are no common elements between any two arrays. The worst-case time complexity of computing the median of the medians of
A
1
,
A
2
,
…
,
A
n
A_1, A_2, \ldots, A_n
A
1
,
A
2
,
…
,
A
n
is
14
CS 2015 Set 1 · 1 mark · MCQ · Easy
Which one of the following is the recurrence equation for the worst case time complexity of the Quicksort algorithm for sorting
n
n
n
(
≥
2
\ge 2
≥
2
) numbers? In the recurrence equations given in the options below,
c
c
c
is a constant.
15
CS 2015 Set 1 · 2 marks · MCQ · Moderate
Consider the following C function.
16
CS 2015 Set 2 · 1 mark · MCQ · Moderate
An unordered list contains
n
n
n
distinct elements. The number of comparisons to find an element in this list that is neither maximum nor minimum is
17
CS 2015 Set 2 · 1 mark · MCQ · Easy
Consider the basic COCOMO model where
E
E
E
is the effort applied in person-months,
D
D
D
is the development time in chronological months,
K
L
O
C
\mathrm{KLOC}
KLOC
is the estimated number of delivered lines of code (in thousands) and
a
b
,
b
b
,
c
b
,
d
b
a_b, b_b, c_b, d_b
a
b
,
b
b
,
c
b
,
d
b
have their usual meanings. The basic COCOMO equations are of the form
18
CS 2015 Set 3 · 1 mark · MCQ · Easy
Consider the equality
∑
i
=
0
n
i
3
=
X
\sum_{i=0}^{n} i^3 = X
∑
i
=
0
n
i
3
=
X
and the following choices for
X
X
X
19
CS 2015 Set 3 · 2 marks · MCQ · Moderate
Assume that a mergesort algorithm in the worst case takes
30
s
e
c
o
n
d
s
30\,\mathrm{seconds}
30
seconds
for an input of size
64
64
64
. Which of the following most closely approximates the maximum input size of a problem that can be solved in
6
m
i
n
u
t
e
s
6\,\mathrm{minutes}
6
minutes
?
20
CS 2015 Set 3 · 2 marks · NAT · Moderate
Suppose
c
=
⟨
c
[
0
]
,
.
.
.
,
c
[
k
−
1
]
⟩
c = \langle c[0], ..., c[k - 1] \rangle
c
=
⟨
c
[
0
]
,
...
,
c
[
k
−
1
]⟩
is an array of length
k
k
k
, where all the entries are from the set {0, 1}. For any positive integers
a
a
a
and
n
n
n
, consider the following pseudocode.
21
CS 2015 Set 3 · 2 marks · MCQ · Hard
Let
f
(
n
)
=
n
f(n) = n
f
(
n
)
=
n
and
g
(
n
)
=
n
(
1
+
sin
n
)
g(n) = n^{(1 + \sin n)}
g
(
n
)
=
n
(
1
+
s
i
n
n
)
, where
n
n
n
is a positive integer. Which of the following statements is/are correct?