##### Differences

This shows you the differences between two versions of the page.

 cs-312:hw9.5 [2014/12/31 15:59]ringger created cs-312:hw9.5 [2014/12/31 16:24] (current)ringger 2014/12/31 16:24 ringger 2014/12/31 15:59 ringger created 2014/12/31 16:24 ringger 2014/12/31 15:59 ringger created Line 17: Line 17: Recurrence Relations: Recurrence Relations: - Suppose an algorithm has running time described by the following recurrence relation: ​<​math>​T(n) = 4 T(n/3) + n^3​.  Use the theory of recurrence relations to solve this recurrence relation. + Suppose an algorithm has running time described by the following recurrence relation: ​$T(n) = 4 T(n/3) + n^3$.  Use the theory of recurrence relations to solve this recurrence relation. * Come up with the general solution. * Come up with the general solution. - * Assume that the smallest instance of the problem solved by this algorithm has size <​math>​n=3 ​and that the running time on that instance is 1 (i.e., ​<​math>​T(3)=1​).  Find the specific solution to the recurrence given this initial condition. + * Assume that the smallest instance of the problem solved by this algorithm has size $n=3$ and that the running time on that instance is 1 (i.e., ​$T(3)=1$).  Find the specific solution to the recurrence given this initial condition. 