Algorithms
Q11.
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 isQ12.
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)); }Q13.
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 .Q14.
Consider the equality \sum_{i=0}^{n}i^{3}=X and the following choices for X I. \Theta (n^{4}) II. \Theta (n^{5}) III. O (n^{5}) IV. \Omega (n^{3}) The equality above remains correct if X is replaced byQ15.
Let f(n)=n and g(n)=n^{1+sin \; n} where n is a positive integer. Which of the following statements is/are correct? I. f(n)=O(g(n)) II. f(n)= \Omega (g(n))Q16.
Consider the following C function. int fun1(int n){ int i,j,k,p,q=0; for (i=1; i\lt n; ++i) { p=0; for (j=n; j\gt 1; j=j/2) ++p; for (k=1; k\lt p; k=k*2) ++q; } return q; } Which one of the following most closely approximates the return value of the function fun1?Q17.
Consider the following function: int unknown(int n){ int i, j, k=0; for (i=n/2; i<=n; i++) for (j=2; j<=n; j=j*2) k = k + n/2; return (k); } The return value of the function isQ18.
Let W(n) and A(n) denote respectively, the worst case and average case running time of an algorithm executed on an input of size n. Which of the following is ALWAYS TRUE?Q19.
Which of the given options provides the increasing order of asymptotic complexityoffunctions f1, f2, f3 and f4? f_{1}(n)=2^{n}; f_{2}(n)=n^{3/2}; f_{3}(n)=nlog_{2}n; f_{4}(n)=n^{log_{2}n}Q20.
Two alternative packages A and B are available for processing a database having 10^{k} records. Package A requires 0.0001n^{2} time units and package B requires 10n \log _{{10}} n time units to process n records. What is the smallest value of k for which package B will be preferred over A?