Multiple choice

Directions: Find the time complexities of the following question.

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

  1. O(n2)

  2. O(nlog 3)

  3. O(n)

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

Using the Master Theorem for recurrence relations of the form T(n) = aT(n/b) + f(n), here a = 3, b = 2, and f(n) = n log n. Comparing f(n) = n log n with n^(log_b a) = n^(log_2 3), since log_2 3 is approximately 1.585, n^1.585 grows faster than n log n. Thus, Case 1 applies, yielding O(n^(log 3)).

Keep practicing — related questions