Algorithms
Q41.
Let T(n) be the function defined by T(1) =1, \: T(n) = 2T (\lfloor \frac{n}{2} \rfloor ) + \sqrt{n} \text{ for } n \geq 2.Which of the following statements is true?Q43.
Consider the following two functions: g_1(n) = \begin{cases} n^3 \text{ for } 0 \leq n \leq 10,000 \\ n^2 \text{ for } n \geq 10,000 \end{cases}g_2(n) = \begin{cases} n \text{ for } 0 \leq n \leq 100 \\ n^3 \text{ for } n > 100 \end{cases}Which of the following is true?Q45.
Let f (n) =n^{2} logn and g(n) = n(logn)^{10} be two positive functions of n. Which of the following statements is correct ?Q46.
The minimum number of comparisons required to find the minimum and the maximum of 100 numbers is _________________.Q47.
If n is a power of 2, then the minimum number of multiplications needed to compute a^n isQ48.
Given below are some algorithms, and some algorithm design paradigms. Match the above algorithms on the left to the corresponding design paradigm they follow.Q50.
Consider a sequence of 14 elements: A = [-5, -10, 6, 3, -1, -2, 13, 4, -9, -1, 4, 12, -3, 0]. The subsequence sum S(i,j)=\sum_{k=i}^{j}A[k]. Determine the maximum of S(i,j), where 0 \leq i \leq j \lt 14. (Divide and conquer approach may be used). Answer:______