Asymptotic Notation

Question 1
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 2
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 3
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 3 Explanation: 
NOTE: Question is excluded from the evaluation due to ambiguity.
Click here for detail solution by gateoverflow
Question 4
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 5
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 6
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 7
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 8
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 9
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 10
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
There are 10 questions to complete.

4 thoughts on “Asymptotic Notation”

Leave a Comment