Multiple choice

Directions: Find the time complexities of the following question.

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

  1. O(n2)

  2. O(n log n)

  3. O(n)

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

The recurrence T(n) = T(2n/3) + 1 has one recursive call that reduces the problem size by factor 2/3, with constant work at each level. The height of the recursion tree is log_(3/2)(n) since we repeatedly multiply by 2/3. With constant work per level, total is O(log n). This matches the claimed answer D.

Keep practicing — related questions