Multiple choice

Directions: Find the time complexities of the following question.

T(n)=3T(n/4)+c(n2)

  1. O(n2)

  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 Master Theorem: a=3, b=4, f(n)=n^2. Since n^(log_4(3)) ≈ n^0.79 < n^2, we're in Case 3 where f(n) dominates. Therefore T(n) = O(n^2). The recursive calls at each level contribute polynomial work, but the n^2 term at the root determines overall complexity.

Keep practicing — related questions