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

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 2022
MCQ (More than One Correct Answer)
+2
-0

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?

A
f(2n $$-$$ 1) = 2n $$-$$ 1
B
f(2n) = 1
C
f(5 . 2n) = 2n + 1 + 1
D
f(2n + 1) = 2n + 1
3
GATE CSE 2021 Set 2
MCQ (Single Correct Answer)
+2
-0.66

For constants a ≥ 1 and b > 1, consider the following recurrence defined on the non-negative integers :

$$T\left( n \right) = a.T\left( {\frac{n}{b}} \right) + f\left( n \right)$$

Which one of the following options is correct about the recurrence T(n)?

A
If f(n) is $$\frac{n}{{{{\log }_2}(n)}}$$, then T(n) is θ(log2(n)).
B
If f(n) is n log2(n), then T(n) is θ(n log2(n)).
C
If f(n) is O(nlogb(a) - ϵ) for some ϵ > 0, then T(n) is θ(nlogb(a)).
D
If f(n) is θ(nlogb(a)), then T(n) is θ(nlogb(a))
4
GATE CSE 2021 Set 1
MCQ (Single Correct Answer)
+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)
GATE CSE Subjects
Software Engineering
Web Technologies
EXAM MAP