Question 1 |
Which one of the following statements is TRUE for all positive functions f(n)?
f(n^2)=\theta (f(n)^2), where f(n) is a polynomial | |
f(n^2)=o (f(n)^2) | |
f(n^2)=O (f(n)^2), where f(n) is an exponential function | |
f(n^2)=\Omega (f(n)^2) |
Question 1 Explanation:
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?
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?
f_3, f_2, f_1 | |
f_2, f_1, f_3 | |
f_1, f_2, f_3 | |
f_2, f_3, f_1 |
Question 2 Explanation:
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?O\left(n^{2}\right) | |
O(n \log n) | |
O(n) | |
O(n \log n \log n) |
Question 3 Explanation:
NOTE: Question is excluded from the evaluation due to ambiguity.
Click here for detail solution by gateoverflow
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 ________ .
O(n) | |
O(n \log n) | |
O(n^2) | |
\Omega(n^2 \log n) |
Question 4 Explanation:
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\theta (n\sqrt{n}) | |
\theta (n^{2}) | |
\theta (n logn) | |
\theta (n^{2} logn) |
Question 5 Explanation:
Question 6 |
Match the algorithms with their time complexities:


P-(iii),Q-(iv), R-(i), S-(ii) | |
P-(iv),Q-(iii), R-(i), S-(ii) | |
P-(iii),Q-(iv), R-(ii), S-(i) | |
P-(iv),Q-(iii), R-(ii), S-(i) |
Question 6 Explanation:
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:
10,\sqrt{n},n, log_{2}n,\frac{100}{n}.
The CORRECT arrangement of the above functions in increasing order of asymptotic complexity is:
log_{2}n,\frac{100}{n}, 10,\sqrt{n},n | |
\frac{100}{n}, 10,log_{2}n, \sqrt{n}, n | |
10, \frac{100}{n}, \sqrt{n}, log_{2}n, n | |
\frac{100}{n}, log_{2}n, 10, \sqrt{n}, n |
Question 7 Explanation:
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?
\Theta (n^{2}) | |
\Theta (n+m) | |
\Theta (m^{2}) | |
\Theta (n^{4}) |
Question 8 Explanation:
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 .


1.58 | |
2.32 | |
2.85 | |
3.55 |
Question 9 Explanation:
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
\Theta (1) | |
\Theta (log(n)) | |
\Theta \sqrt{n} | |
\Theta (n) |
Question 10 Explanation:
There are 10 questions to complete.
Please correct the right options for Q41:
Except a all are true.
Please Update the Q.22’s Option A. Correct answer is log (n)
Question no. 27 have typing mistake
i/2 is wrong
It’s is i/=2
Question Updated.