# Asymptotic Notation

 Question 1
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 1 Explanation:
 Question 2
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 2 Explanation:
NOTE: Question is excluded from the evaluation due to ambiguity.
Click here for detail solution by gateoverflow
 Question 3
There are n unsorted arrays: $A_1,A_2,...,A_n$. Assume that n is odd. Each of $A_1,A_2,...,A_n$ contains n distinct elements. There are no common elements between any two arrays. The worst-case Asymptotic Notation of computing the median of the medians of $A_1,A_2,...,A_n$ is ________ .
 A $O(n)$ B $O(n \log n)$ C $O(n^2)$ D $\Omega(n^2 \log n)$
GATE CSE 2019   Algorithm
Question 3 Explanation:
 Question 4
Consider the following C function

int fun (int n) {
int i, j;
for (i = 1; i < = n; i++) {
for (j = 1 ; j < n ; j+=i) {
printf ("%d %d , i, j ) ;
}
}
}
Asymptotic Notation of fun in terms of $\theta$ notation is
 A $\theta (n\sqrt{n})$ B $\theta (n^{2})$ C $\theta (n logn)$ D $\theta (n^{2} logn)$
GATE CSE 2017 SET-2   Algorithm
Question 4 Explanation:
 Question 5
Match the algorithms with their time complexities:
 A P-(iii),Q-(iv), R-(i), S-(ii) B P-(iv),Q-(iii), R-(i), S-(ii) C P-(iii),Q-(iv), R-(ii), S-(i) D P-(iv),Q-(iii), R-(ii), S-(i)
GATE CSE 2017 SET-2   Algorithm
Question 5 Explanation:
 Question 6
Consider the following functions from positive integers to real numbers:

$10,\sqrt{n},n, log_{2}n,\frac{100}{n}$.

The CORRECT arrangement of the above functions in increasing order of asymptotic complexity is:
 A $log_{2}n,\frac{100}{n}, 10,\sqrt{n},n$ B $\frac{100}{n}, 10,log_{2}n, \sqrt{n}, n$ C $10, \frac{100}{n}, \sqrt{n}, log_{2}n, n$ D $\frac{100}{n}, log_{2}n, 10, \sqrt{n}, n$
GATE CSE 2017 SET-1   Algorithm
Question 6 Explanation:
 Question 7
In an adjacency list representation of an undirected simple graph G = (V,E), each edge (u,v) has two adjacency list entries: [v] in the adjacency list of u, and [u] in the adjacency list of v. These are called twins of each other. A twin pointer is a pointer from an adjacency list entry to its twin. If |E|=m and |V|=n, and the memory size is not a constraint, what is the Asymptotic Notation of the most efficient algorithm to set the twin pointer in each entry in each adjacency list?
 A $\Theta (n^{2})$ B $\Theta (n+m)$ C $\Theta (m^{2})$ D $\Theta (n^{4})$
GATE CSE 2016 SET-2   Algorithm
Question 7 Explanation:
 Question 8
The given diagram shows the flowchart for a recursive function A(n). Assume that all statements, except for the recursive calls,have O(1) Asymptotic Notation. If the worst case Asymptotic Notation of this functionis $O(n^{\alpha })$, then the least possible value(accurate upto two decimal positions) of $\alpha$ is .
 A 1.58 B 2.32 C 2.85 D 3.55
GATE CSE 2016 SET-2   Algorithm
Question 8 Explanation:
 Question 9
Consider a carry lookahead adder for adding two n-bit integers,built using gates of fan-in at most two. The time to perform addition using this adder is
 A $\Theta (1)$ B $\Theta (log(n))$ C $\Theta \sqrt{n}$ D $\Theta (n)$
GATE CSE 2016 SET-1   Algorithm
Question 9 Explanation:
 Question 10
The time complexity of the following C function is (assume n>0)
 int recursive (int n) {
if(n == 1)
return (1);
else
return (recursive (n-1) + recursive (n-1));
}
 A O(n) B $O(n \log n)$ C $O\left(n^{2}\right)$ D $O\left(2^{n}\right)$
ISRO CSE 2015   Algorithm
Question 10 Explanation:
There are 10 questions to complete.

### 2 thoughts on “Asymptotic Notation”

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

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

Reply