1
GATE CSE 2023
MCQ (More than One Correct Answer)
+2
-0.67

Consider functions Function_1 and Function_2 expressed in pseudocode as follows:

Function 1
while n > 1 do
for i = 1 to n do
x = x + 1;
end for
n = n/2;
end while

Function 2
for i = 1 to 100 ∗ n do
x = x + 1;
end for

Let $$f_1(n)$$ and $$f_2(n)$$ denote the number of times the statement "$$x=x+1$$" is executed in Function_1 and Function_2, respectively.

Which of the following statements is/are TRUE?

A
$${f_1}(n) \in \Theta ({f_2}(n))$$
B
$${f_1}(n) \in o({f_2}(n))$$
C
$${f_1}(n) \in \omega ({f_2}(n))$$
D
$${f_1}(n) \in O(n)$$
2
GATE CSE 2021 Set 1
+2
-0.67

Consider the following three functions.

f1 = 10n, f2 = nlogn, f3 = n√n

Which one of the following options arranges the functions in the increasing order of asymptotic growth rate?

A
f1 , f2, f3
B
f2, f1, f3
C
f3, f2, f1
D
f2, f3, f1
3
GATE CSE 2021 Set 1
+2
-0.67

Consider the following recurrence relation.

$$T(n) = \left\{ {\begin{array}{*{20}{c}} {T(n/2) + T(2n/5) + 7n \ \ \ if\ n > 0}\\ {1\ \ \ \ \ \ \ if\ n = 0} \end{array}} \right.$$

Which one of the following option is correct?

A
T(n) = Θ(n log n)
B
T(n) = Θ(n5/2)
C
T(n) = Θ((log n)5/2)
D
T(n) = Θ(n)
4
GATE CSE 2019
+2
-0.67
There are n unsorted arrays: A1, A2, ..., An. Assume that n is odd. Each of A1, A2, ..., An contains 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 A1, A2, ..., An is
A
$$O\left( n \right)$$
B
$$O\left( {n\log n} \right)$$
C
$$O\left( {{n^2}\log n} \right)$$
D
$$O\left( {{n^2}} \right)$$
GATE CSE Subjects
EXAM MAP
Medical
NEET