For m > 1 and T(1) = 1, what is the tight asymptotic bound for the recurrence…

UGC NET 2013Modified — slightly modified from the official paper; see the solution

For m > 1 and T(1) = 1, what is the tight asymptotic bound for the recurrence T(n) = m T(n/2), with n a power of 2?

  1. A.

    O(n²)

  2. B.

    O(n^(lg m))

  3. C.

    O(n² lg n)

  4. D.

    O(n lg n)

Attempted by 8 students.

Sign up free to check your answer

Sign up free

Explore the full course: Uppsc Polytechnic Lecturer 2025 Cs

Loading lesson…