For constants a ≥ 1 and b > 1, consider the following recurrence defined on the non-negative integers:\(T\left( n \right) = a.T\left( {\frac{n}{b}} \right) + f\left( n \right)\)Which one of the following options is correct about the recurrence T(n)?

If f(n) is θ(nlogb(a)), then T(n) is θ(nlogb(a))

If f(n) is \(\frac{n}{{{{\log }_2}(n)}}\), then T(n) is θ(log2(n)).

If f(n) is n log2(n), then T(n) is θ(n log2(n)).

If f(n) is O(nlogb(a) - ϵ) for some ϵ > 0, then T(n) is θ(nlogb(a)).

For constants a ≥ 1 and b > 1, consider the following recurrence de

1.	For constants a ≥ 1 and b > 1, consider the following recurrence defined on the non-negative integers:\(T\left( n \right) = a.T\left( {\frac{n}{b}} \right) + f\left( n \right)\)Which one of the following options is correct about the recurrence T(n)?
A.	If f(n) is \(\frac{n}{{{{\log }_2}(n)}}\), then T(n) is θ(log2(n)).
B.	If f(n) is n log2(n), then T(n) is θ(n log2(n)).
C.	If f(n) is O(nlogb(a) - ϵ) for some ϵ > 0, then T(n) is θ(nlogb(a)).
D.	If f(n) is θ(nlogb(a)), then T(n) is θ(nlogb(a))
Answer» D. If f(n) is θ(nlogb(a)), then T(n) is θ(nlogb(a))

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?

For constants a ≥ 1 and b > 1, consider the following recurrence defined on the non-negative integers:\(T\left( n \right) = a.T\left( {\frac{n}{b}} \right) + f\left( n \right)\)Which one of the following options is correct about the recurrence T(n)?

Discussion

No Comment Found

Related MCQs

Reply to Comment