InterviewSolution
Saved Bookmarks
InterviewSolution
| 1. |
What is the solution of the recursive equation T(n)=3T(n/4)+n12? |
|
Answer» tion:Assume that a recurrence RELATION is given as below:T(n)=3T(n/4)+NT(n)=3T(n/4)+nand 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)+nEquation 2: T(n/4)=3T(n/(42))+n/4T(n/4)=3T(n/(42))+n/4Equation 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 |
|