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)