2 ms·
Interesting: "The growth pattern is: 0, 4, 8, 16, 25, 35, 46, 58, 72, 88, ..." What is the big-o amortized cost of using this pattern? Doubling has a easy pro
by mcguire 8y ago
Interesting:
"The growth pattern is: 0, 4, 8, 16, 25, 35, 46, 58, 72, 88, ..."
What is the big-o amortized cost of using this pattern? Doubling has a easy proof that it's O(1) amortized.
- eatitraw 8y agoThe growth pattern is still exponential, instead of going x -> 2 * x, you go x -> 9/8 * x + 6. I think it should still be O(1) amortized, you just need to adjust your proof for doubling a bit.
- rurban 8y agoMathematically the best is not doubling but fibonacci. for the start doubling is used because it's much faster to compute.