Multiple choice

Directions: Find the time complexities of the following question.

T(n)=3T(n/4)+nlogn

  1. O(n2)

  2. O(n log n)

  3. O(n)

  4. O(log n)
Reveal answer Fill a bubble to check yourself
B Correct answer
Explanation

Using Master Theorem: a=3, b=4, f(n)=n log n. Since n^(log_4(3)) ≈ n^0.79 < n log n, we're in Case 3 where f(n) dominates by a polynomial factor. Therefore T(n) = O(n log n), which matches the claimed answer B.

Keep practicing — related questions