Consider the following recurrenceT(n) = 2T(\(\sqrt n\)) + 1T(1) = 1Which of the following is true?

Consider the following recurrenceT(n) = 2T(\(\sqrt n\)) + 1T(1) = 1Whi

1.	Consider the following recurrenceT(n) = 2T(\(\sqrt n\)) + 1T(1) = 1Which of the following is true?
A.	T(n) = O(log log n)
B.	T(n) = O(log n)
C.	T(n) = O(\(\sqrt n\))
D.	T(n) = O(n)
Answer» C. T(n) = O(\(\sqrt n\))

Discussion

No Comment Found

Related MCQs

Consider the following segment of C codeint j, n;j = 1;while (j<=n) j = j*2;The number of comparisons made in the execution of the loop for any n > 0 is
Consider the following functions from positive integers t 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:
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) = Ω(g(n))
Consider the algorithm that solves problems of size n by recursively solving two sub problems of size n - 1 and then combining the solutions in constant time. Then the running time of the algorithm would be:
Consider the following three functions.f1 = 10n f2 = nlogn f3 = n√nWhich one of the following options arranges the functions in the increasing order of asymptotic growth rate?
If algorithm A and another algorithm B take log2(n) and √n microseconds, respectively, to solve a problem, then the largest size n of a problem these algorithms can solve. respectively. in one second are_____ and _____.
If positive function f(n) is given below as:f(n) = a0 + a1n + a2n2 + a3n3 + .......amnm then for positive n and am > 0, f(n) is:
Consider the equality \(\mathop \sum \limits_{i = 0}^n {i^3} = X\) and the following choices for
Consider the following C function.int fun1(int n) {int i, j, k, p, q = 0;for (i = 1; i p = 0;for (j = n; j > 1; j = j/2) ++ p;for (k = 1; k ++ q;}return q;}Which one of the following most closely approximates the return value of the function fun1?
Consider the following recurrenceT(n) = 2T(\(\sqrt n\)) + 1T(1) = 1Which of the following is true?

Consider the following recurrenceT(n) = 2T(\(\sqrt n\)) + 1T(1) = 1Which of the following is true?

Discussion

No Comment Found

Related MCQs

Reply to Comment