Which of the following is the solution of the following recurrence relation…

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

Observe how n changes per recursive level:

After k levels the problem size is (2/3)^k · n. We stop when the size is about 1, so (2/3)^k · n = 1.

Solving for k gives k = log_{3/2} n = Theta(log n).

• Work per level: 1 (a constant).

• Number of levels: Θ(log n)

• Total work: sum of constant 1 over Θ(log n) levels = Θ(log n)

Conclusion: T(n) = Θ(log n)