GATE 2023 CS – Question 29
Algorithms · Asymptotic Analysis and Time/Space Complexity · 1 mark · Multiple select
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)$
Practise this question in The GATE Grind →
Show answer and explanation
Correct answer: (A) $f \in O(g)$; (C) $f \in o(g)$
Explanation
n grows strictly slower than n², since n/n² → 0. So f ∈ O(g) and f ∈ o(g), while f ∉ Ω(g) and f ∉ Θ(g).
More Asymptotic Analysis and Time/Space Complexity questions
- GATE 2023 CS Q54 – Consider functions Function 1 and Function 2 expressed in pseudocode as follows: Let f…
- GATE 2022 CS Q11 – Which one of the following statements is TRUE for all positive functions f(n)?
- GATE 2022 CS Q51 – Consider the following recurrence: f(1)=1; f(2n)=2f(n)-1, for n1; f(2n+1)=2f(n)+1, for n1.…
- GATE 2021 CS (CS1) Q13 – Consider the following three functions. f 1 = 10n, f 2 = n n, f 3 = nn Which one of the…
- GATE 2021 CS (CS1) Q40 – Consider the following recurrence relation. T(n) = T(n/2) + T(2n/5) + 7n if n>0; T(n)=1 if…
- GATE 2020 CS Q12 – For parameters a and b, both of which are (1), T(n)=T(n1/a)+1, and T(b)=1. Then T(n) is
All Asymptotic Analysis and Time/Space Complexity questions →