The recurrence relation T(1) = 2 T(n) = 3T(n/4)+n has the solution, T(n)…

The standard format for the Master Theorem is:

T(n) = a * T(n/b) + f(n)

From our given recurrence relation:

T(n) = 3 * T(n/4) + n

We can identify the constants and functions:

• a = 3 (number of subproblems)

• b = 4 (subproblem size factor)

• f(n) = n (work done at the current level)

Next, we calculate the critical value, which is nlogb (a):

• Value = n^(log_4(3))

Let's approximate the value of log_4(3):

• Since 3 is less than 4, log_4(3) is strictly less than 1.

• Specifically, log_4(3) is approximately 0.793.

• Therefore, the critical term is n^0.793.

Now, we compare our work function f(n) = n (which is n^1) against the critical term n^0.793:

• f(n) grows strictly faster than n^log_4(3) because 1 > 0.793.

• This falls under Case 3 of the Master Theorem (where the driver function f(n) dominates the computation).

According to Case 3 of the Master Theorem, if f(n) is polynomially larger than n^log_b(a), the solution to the recurrence is governed entirely by the f(n) term:

T(n) = O(f(n))
T(n) = O(n)

Correct Answer: A