Multiple choice

Directions: Find the time complexities of the following question.

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

  1. O(n2)

  2. O(n log n)

  3. O(n)

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

The recurrence T(n) = T(n/3) + T(2n/3) + O(n) creates a highly unbalanced recursion tree where each level's work sums to O(n). The height is approximately log_(3/2)(n) because the larger branch shrinks by factor 2/3. Total work: O(n log n). This is correct.

Keep practicing — related questions