GATE CSE 2025 Set 1 | Complexity Analysis and Asymptotic Notations Question 1 | Algorithms

GATE CSE 2025 Set 1

MCQ (Single Correct Answer)

-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?

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

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

$T(n)=\Theta\left((\log n)^2 2^n\right)$

$T(n)=\Theta\left(4^n\right)$

GATE CSE 2024 Set 2

MCQ (Single Correct Answer)

-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?

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

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

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

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

GATE CSE 2024 Set 1

MCQ (Single Correct Answer)

-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

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

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

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

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

GATE CSE 2023

MCQ (More than One Correct Answer)

-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?

$$f \in O(g)$$

$$f \in \Omega (g)$$

$$f \in o(g)$$

$$f \in \Theta (g)$$