The solution of the recurrence relation of T(n) = 3T(floor(n/4)) + n is

Explanation

T(n) = 3T(n/4) + n. Here a = 3, b = 4, f(n) = n and n^(log₄3) ≈ n^0.79. Since f(n) = n grows polynomially faster than n^(log₄3), case 3 of the master theorem gives T(n) = Θ(n). So T(n) = O(n) (it is also O(n²), but (c) is the tight bound and the best choice).