What is the solution of the recurrence T(n) = 3T(n/2) + n ?

Explanation

Here a = 3, b = 2 so n^(log₂3) ≈ n^1.58 dominates f(n) = n, and case 1 of the Master theorem gives Θ(n^(log₂3)).