They were somewhat linear with relation to capacity of memory, but they also might not have been possible with capacity from a decade ago.

This is easily seen if you look at fun algorithms such as BDDs. If you have the memory for them, they are amazingly fast. But, if you don't have the memory for it, it gets you nothing.

Edit: removed a "not" that I didn't mean to type. :(