1
GATE CSE 2025 Set 1
MCQ (Single Correct Answer)
+1
-0.33

Consider the following recurrence relation :

$$T(n)=2 T(n-1)+n 2^n \text { for } n>0, T(0)=1$$

Which ONE of the following options is CORRECT?

A
$T(n)=\Theta\left(n^2 2^n\right)$
B
$T(n)=\Theta\left(n 2^n\right)$
C
$T(n)=\Theta\left((\log n)^2 2^n\right)$
D
$T(n)=\Theta\left(4^n\right)$
2
GATE CSE 2024 Set 2
MCQ (Single Correct Answer)
+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)$

3
GATE CSE 2024 Set 1
MCQ (Single Correct Answer)
+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)$

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

Let $$f$$ and $$g$$ be functions of natural numbers given by $$f(n)=n$$ and $$g(n)=n^2$$. Which of the following statements is/are TRUE?

A
$$f \in O(g)$$
B
$$f \in \Omega (g)$$
C
$$f \in o(g)$$
D
$$f \in \Theta (g)$$
GATE CSE Subjects
Software Engineering
Web Technologies
EXAM MAP