The asymptotic upper bound solution of the recurrence relation given by \(T(n)…

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

The asymptotic upper bound solution of the recurrence relation given by

T(n)=2T(n2)+nlg⁡ nT(n) = 2T \left( \frac{n}{2} \right) +\frac{n}{\lg \: n}

  1. A.

    O(n2)O(n^2)

  2. B.

    O(n lg⁡ n)O(n \:\lg \: n )

  3. C.

    O(n lg⁡ lg⁡ n)O(n \:\lg \:\lg \: n)

  4. D.

    O(lg⁡ lg⁡ n)O(\lg \:\lg \: n)

Attempted by 76 students.

Sign up free to check your answer

Sign up free

Explore the full course: Uppsc Polytechnic Lecturer 2025 Cs

Loading lesson…