Question

What is the solution of the recursive equation T(n)=3T(n/4)+n12?

Answer 1

Explanation:

Assume that a recurrence relation is given as below:

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

and we know that T(1)=2T(1)=2.

We want to solve the relation (find an explicit definition of T(n)T(n) which does not rely on itself).

My solving:

Equation 1: T(n)=3T(n/4)+nT(n)=3T(n/4)+n

Equation 2: T(n/4)=3T(n/(42))+n/4T(n/4)=3T(n/(42))+n/4

Equation 3: T(n/(42))=3T(n/(43))+n/(42)T(n/(42))=3T(n/(43))+n/(42)

Substituting the equations (2) and (3) in (1), we get T(n)=(33)T(n/(43))+((32)n)/42+3n/4+nT(n)=(33)T(n/(43))+((32)n)/42+3n/4+n.

Generalizing it we get T(n)=(3k