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

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

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

If f(n) is n log 2 (n), then T(n) is θ(n log 2 (n)).

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

If f(n) is θ(n logb (a) ), then T(n) is θ(n log b (a) )

GATE Computer Science (CS) 2021 Shift 2 Solved Paper

Question : 49 of 65

Marks: +1, -0

For constants a ≥ 1 and b > 1, consider the following recurrence defined on the non-negative integers:

T (n) = a.T (\;{n}/{b}) + f (n)

Which one of the following options is correct about the recurrence T(n)?

Go to Question:

Prev Question

Next Question