# Asymptotic Notation

 Question 1
Consider functions Function 1 and Function 2 expressed in pseudocode as follows:

Let $f_1(n)$ and $f_2(n)$ denote the number of times the statement $"x = x + 1"$ is executed in Function 1 and Function 2, respectively.
Which of the following statements is/are TRUE?
 A $f_1(n)\in \Theta (f_2(n))$ B $f_1(n)\in o (f_2(n))$ C $f_1(n)\in \omega (f_2(n))$ D $f_1(n)\in O (n)$
GATE CSE 2023   Algorithm
Question 1 Explanation:
 Question 2
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 2023   Algorithm
Question 2 Explanation:

 Question 3
Which one of the following statements is TRUE for all positive functions $f(n)$?
 A $f(n^2)=\theta (f(n)^2)$, where $f(n)$ is a polynomial B $f(n^2)=o (f(n)^2)$ C $f(n^2)=O (f(n)^2)$, where $f(n)$ is an exponential function D $f(n^2)=\Omega (f(n)^2)$
GATE CSE 2022   Algorithm
Question 3 Explanation:
 Question 4
Consider the following three functions.

$f_1=10^n\; f_2=n^{\log n}\;f_3=n^{\sqrt {n}}$

Which one of the following options arranges the functions in the increasing order of asymptotic growth rate?
 A $f_3, f_2, f_1$ B $f_2, f_1, f_3$ C $f_1, f_2, f_3$ D $f_2, f_3, f_1$
GATE CSE 2021 SET-1   Algorithm
Question 4 Explanation:
 Question 5
What is the complexity of the following code?
 sum=0;
for(i=1;i<=n;i*=2)
for(j=1;j<=n;j++)
sum++;
Which of the following is not a valid string?
 A $O\left(n^{2}\right)$ B $O(n \log n)$ C $O(n)$ D $O(n \log n \log n)$
ISRO CSE 2020   Algorithm
Question 5 Explanation:
NOTE: Question is excluded from the evaluation due to ambiguity.

There are 5 questions to complete.

### 7 thoughts on “Asymptotic Notation”

1. Please correct the right options for Q41:
Except a all are true.

2. Please Update the Q.22’s Option A. Correct answer is log (n)

3. Question no. 27 have typing mistake
i/2 is wrong
It’s is i/=2