GATE CSE 2023 | Complexity Analysis and Asymptotic Notations Question 4 | Algorithms

GATE CSE 2023

MCQ (More than One Correct Answer)

-0.33

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)$$

GATE CSE 2022

MCQ (Single Correct Answer)

-0.33

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

f(n²) = $$\theta$$(f(n)²), when f(n) is a polynomial

f(n²) = o(f(n)²)

f(n²) = O(f(n)²), when f(n) is an exponential function

f(n²) = $$\Omega$$(f(n)²)

GATE CSE 2020

MCQ (Single Correct Answer)

-0.33

For parameters a and b, both of which are $$\omega \left( 1 \right)$$,
T(n) = $$T\left( {{n^{1/a}}} \right) + 1$$, and T(b) = 1.
Then T(n) is

$$\Theta \left( {{{\log }_a}{{\log }_b}n} \right)$$

$$\Theta \left( {{{\log }_{ab}}n} \right)$$

$$\Theta \left( {{{\log }_b}{{\log }_a}n} \right)$$

$$\Theta \left( {{{\log }_2}{{\log }_2}n} \right)$$

GATE CSE 2015 Set 3

MCQ (Single Correct Answer)

-0.3

Consider the equality $$\sum\limits_{i = 0}^n {{i^3}} = X$$ and the following choices for $$X$$
$$\eqalign{ & \,\,\,\,\,\,\,{\rm I}.\,\,\,\,\,\,\Theta \left( {{n^4}} \right) \cr & \,\,\,\,\,{\rm I}{\rm I}.\,\,\,\,\,\,\Theta \left( {{n^5}} \right) \cr & \,\,\,{\rm I}{\rm I}{\rm I}.\,\,\,\,\,\,O\left( {{n^5}} \right) \cr & \,\,\,{\rm I}V.\,\,\,\,\,\,\Omega \left( {{n^3}} \right) \cr} $$
The equality above remains correct if $$𝑋$$ is replaced by

Only $${\rm I}$$

Only $${\rm II}$$

$${\rm I}$$ or $${\rm III}$$ or $${\rm IV}$$ but not $${\rm II}$$

$${\rm II}$$ or $${\rm III}$$ or $${\rm IV}$$ but not $${\rm I}$$

PREVIOUS NEXT