Multiple choice

Directions: Find the time complexities of the following question.

T(n)=2T(√n)+nlogn+n

  1. Ω(n2)

  2. Ω(nlog3)

  3. Ω(2n)

  4. None of these
Reveal answer Fill a bubble to check yourself
D Correct answer
Explanation

The recurrence T(n) = 2T(√n) + n log n + n requires a different technique. Let m = log n, then T(2^m) = 2T(2^(m/2)) + 2^m * m + 2^m. This recurrence doesn't yield any of the simple forms in options A, B, or C. The complexity involves polynomial-logarithmic terms that don't match the given options, making 'None of these' the correct choice.

Keep practicing — related questions