September 10, 2001 | Quantitative Analysis of Memoization | Slide #13 |

We win if *hf* > *K*

Suppose

*f*is really really small*hf*is even smallerPerhaps close to zero

We can't win in such a case

As Walt unfortunately found out

*f*was the time to do one multiplicationThis is a budget of time that

*K*must not exceedIf

*K*does even one multiplication, it blows the budget

Next | Copyright © 2001 M-J. Dominus |