1
GATE CSE 2024 Set 2
+1
-0.33

Let $T(n)$ be the recurrence relation defined as follows:

$T(0) = 1$
$T(1) = 2$, and
$T(n) = 5T(n - 1) - 6T(n - 2)$ for $n \geq 2$

Which one of the following statements is TRUE?

A

$T(n) = \Theta(2^n)$

B

$T(n) = \Theta(n2^n)$

C

$T(n) = \Theta(3^n)$

D

$T(n) = \Theta(n3^n)$

2
GATE CSE 2024 Set 1
+1
-0.33

Given an integer array of size $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

A

both $O(N)$ and $\Omega(N)$

B

$O(N)$ but not $\Omega(N)$

C

$\Omega(N)$ but not $O(N)$

D

neither $O(N)$ nor $\Omega(N)$

3
GATE CSE 2022
+1
-0.33

Which one of the following statements is TRUE for all positive functions f(n) ?

A
f(n2) = $$\theta$$(f(n)2), when f(n) is a polynomial
B
f(n2) = o(f(n)2)
C
f(n2) = O(f(n)2), when f(n) is an exponential function
D
f(n2) = $$\Omega$$(f(n)2)
4
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?

A
f(2n $$-$$ 1) = 2n $$-$$ 1
B
f(2n) = 1
C
f(5 . 2n) = 2n + 1 + 1
D
f(2n + 1) = 2n + 1
GATE CSE Subjects
EXAM MAP
Medical
NEET