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 |
||
---|---|---|---|

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</math>. 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</math> and that the running time on that instance is 1 (i.e., <math>T(3)=1</math>). 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. |