Which of the following is the solution of the recurrence T(n) = T(2n/3) + 1?

1. AΘ(n²)
2. BΘ(log n)
3. CΘ(n log n)
4. DΘ(n^(3/2))

Pick an option to check yourself, or open the answer below.

Show answer & explanation

Correct answer: B. Θ(log n)

Explanation

a = 1, b = 3/2, so n^(log_b a) = n⁰ = 1 = f(n). Master theorem case 2 gives Θ(log n) — it is like binary search with a 2/3 split.