Algorithms
Q31.
Consider the following C-program fragment in which i, j,and n are integer variables. for (i = n, j = 0; i > 0; i/=2, j += i); Let Val(j) denote the value stored in the variable j after termination of the for loop. Which one of the following is true?Q32.
Consider the following C-function: double foo (int n) { int i; double sum; if (n = = 0) return 1.0; else { sum = 0.0; for (i = 0; i < n; i++) sum += foo (i); return sum; } } The Asymptotic Notation of space complexity of the above function is:Q33.
Let f(n), g(n) and h(n) be functions defined for positive integers such that f(n) = O(g(n)), \; g(n) \neq O(f(n)), \; g(n) = O(h(n)), \text{ and } h(n) = O(g(n)). Which one of the following statements is FALSE?Q34.
The Asymptotic Notation of the following C function is (assume n \gt 0) int recursive (int n) { if (n == 1) return (1); else return (recursive (n - 1) + recursive (n - 1)); }Q35.
Let A[1,..., n] be an array storing a bit (1 or 0) at each location, and f(m) is a function whose Asymptotic Notation is \theta(m). Consider the following program fragment written in a C like language: counter = 0; for (i = 1; i < = n; i++) { if (A[i] == 1) counter++; else { f(counter); counter = 0; } } The complexity of this program fragment isQ36.
The cube root of a natural number n is defined as the largest natural number m such that m^{3}\leq n. The complexity of computing the cube root of n(n is represented in binary notation) isQ37.
Consider the following three claims 1. (n+k)^{m}=\ominus (n^{m}) , where k and m are constants 2. 2^{n+1}=O(2^{n}) 3. 2^{2n+1}=O(2^{n}) Which of these claims are correct?Q38.
Consider the following functions f(n) = 3n^{\sqrt{n}} g(n) = 2^{\sqrt{n}{\log_{2}n}} h(n) = n! Which of the following is true?Q39.
Let S be a sorted array of n integers. Let T(n) denote the time taken for the most efficient algorithm to determined if there are two elements with sum less than 1000 in S. Which of the following statement is true?Q40.
If T_1 = O(1), give the correct matching for the following pairs: \begin{array}{l|l}\hline \text{(M) $T_n = T_{n-1} + n$} & \text{(U) $T_n = O(n)$} \\\hline \text{(N) $T_n = T_{n/2} + n$} & \text{(V) $T_n = O(n \log n)$} \\\hline \text{(O) $T_n = T_{n/2} + n \log n$} & \text{(W) $T_n = O(n^2)$} \\\hline \text{(P) $T_n = T_{n-1} + \log n$} & \text{(X) $T_n = O(\log^2 n)$} \\\hline \end{array}