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 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 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 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 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.
Click here for detail solution by gateoverflow


There are 5 questions to complete.

7 thoughts on “Asymptotic Notation”

Leave a Comment