Hacker Newsnew | past | comments | ask | show | jobs | submitlogin

In order for append-to-back to have O(1) amortised running time, the capacity needs to be multiplied by some constant >1. Any constant would do just fine in terms of complexity, but 2 is the obvious simple choice, being the first integer greater than 1.

If the capacity is only increased by some constant each time, rather than multiplied, this leads to O(n^2) running time for a sequence of n append-to-back operations, surely something to be avoided.



Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: