What will be the complexity of quick sort if the median of n element can be found in O(n) times and remain select as pivot.
-
Solution
Median is selected in O(n) time and remains also in n time so it will take θ(n2)
A recurrence T(n) =2T[(n/4)]+\(\sqrt{n}\) is
-
Solution
T(n) =2T[(n/4)]+\(\sqrt{n}\)
Apply Master’s Theorem
a = 2, b = 4, f(n)=\(\sqrt{n}\)
n\(^{log_{b}2}\)=n\(^{log_{2}4}\)
\(n\left ( \frac{1}{2} \right )\Rightarrow \sqrt{n}\)
then case 2 applied
T(n) =(\(\sqrt{n}\) log n)
Consider the following NFA :
Which of the following strings is not accepted by the automaton?
-
Solution
All strings are accepted
(a)(S, aaaab)→(P, aaab)→(T,aab)→(T,ab)→(T, b)→F
(b)(S, aabbba)→(P, abbba)→(T, bbba)→(Q, bbba)→Q, (bba)→(Q, ba)→(Q, a)→F
(c)(S, abb)→(P, bb) →(R, b)→F
Hence, option (d) is true.
A list of n elements is divided into n/k groups such that in each group k-elements are present. Initially, we have applied insertion sort in each group of making every individual group a sorted list. Now,we have applied merge pass till all the list become a sorted list of n elements. What is the total complexity of this sorting algorithm?
-
Solution
Complexity for every individual group, since we use insertion sort = O(k2)
For all groups =n⁄k×k2=O(nk)
Total number of merge pass required ⇒ log2n⁄k
Complexity of every merge pass = O(n)
Total complexity of merge sort =nlog2n⁄k
= n[log2n – log2k]
Total complexity using insertion sort and merge sort
= nk + n[log2– log2k]
= n[k+ log2n – log2k]
Consider the following code:
int f (int A [Size] [Size], int n)
{
int i, j, s = 0 ;
for (i = 0;i < n; ++1) { if (i % 2== 0) for (j =0; j <= i; j = j+ 1) s= s+ A [i] [j]; else for (j =n – 1; j >= 1; j = j – 1)
s = s +A [i] [j];
}
}
What is the time complexity of code in term of n?
A point on a curve is said to be an extremum if it is a local minimum or a local maximum. The number of distinct extrema for the curve 3x4– 16x3+ 24x2+ 37 is
The minimum number of equal length subintervals needed to approximate \(\int_{1}^{2}xe^{x}\) to an accuracy of at least 1⁄3×10-6´using the trapezoidal rule is _________
-
Solution
1000e
\(\int_{1}^{2}xe^{x}dx=xe^{x}-e^{x}=\left [ e^{x}(x-1) \right ]_{1}^{2}\)
=1000e using trapezoidal rule
The 2n vertices of graph G correspond to all subsets of a set of size n,for n≥6. Two vertices of G are adjacent if and only if the corresponding sets intersect inexactly two elements.The number of vertices of degree zero in G is ________
-
Solution
n + 1
Vertices of degree zero will be those subsets which do not have two elements common with any other subset. This is true only for the subsets of cardinality 0 and 1.
Number of sets with cardinality 1 = n
Number of vertices of degree 0= n + 1
Consider the matrix as given below :\(\begin{bmatrix} 1 & 2 & 3\\ 0 & 4 & 7\\ 0 & 0 & 3 \end{bmatrix}\)
Which one of the following options provides the CORRECT values of the eigenvalues of the matrix ?
-
Solution
Given matrix is upper triangular matrix and its diagonal elements are its eigen values = 1, 4,3
Suppose we uniformly and randomly select a permutation from the 20! permutations of 1, 2, 3…, 20. The probability that 2 appears at an earlier position than any other even number in the selected permutation is ______