The solution of the recurrence relation T(m) = T(3 m/4) + 1 is :

1. Aθ (lg m)
2. Bθ (m)
3. Cθ (mlg m)
4. Dθ (lglg m)

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

Show answer & explanation

Correct answer: A. θ (lg m)

Explanation

The problem shrinks by a constant factor each step with O(1) work, so the depth is log_{4/3} m: Θ(lg m) (Master theorem case 2 with a = 1, b = 4/3).