Multiple choice

Directions: Find the time complexities of the following question.

T(n)=9T(n/3)+n

  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=9, b=3, f(n)=n. Critical exponent: log_3(9)=2, so n^(log_b(a))=n^2. Since f(n)=n < n^2, we're in Case 1 where the recursive part dominates. Therefore T(n) = O(n^2). This matches the claimed answer A - this recurrence represents 9 recursive calls each on 1/3 of the input.

Keep practicing — related questions