Multiple choice

Directions: Find the time complexities of the following question.

T(n)=4T(n/2)+n2√n

  1. O(n2√n)

  2. O(n log n)

  3. O(n)

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

Using the Master Theorem: a=4, b=2, so n^(log_b a) = n^2. The function f(n) = n²√n = n^2.5 is polynomially larger than n^2 (by factor n^0.5). Since the regularity condition a·f(n/b) ≤ c·f(n) holds, case 3 applies: T(n) = Θ(f(n)) = Θ(n²√n). The n log n option would only apply if f(n) = O(n^2), which is false here.

Keep practicing — related questions