Multiple choice

Directions: Find the time complexities of the following question.

2T(n/2)+n2

  1. O(n2)

  2. O(nlog3)

  3. O(2n)

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

Using the Master Theorem: T(n) = 2T(n/2) + n^2, we have a=2, b=2, f(n)=n^2. Since n^log_b(a) = n^1 and f(n) = n^2 = Ω(n^(1+ε)) for ε<1, this is Case 3. The regularity condition 2f(n/2) = n^2/2 ≤ cn^2 holds, so T(n) = Θ(n^2). Options B, C, and D do not match this result.

Keep practicing — related questions