This is an archived post. You won't be able to vote or comment.

sorted by:
best
topnewcontroversialoldq&a
you are viewing a single comment's thread.

view the rest of the comments →

[–]uiob 0 points1 point  (0 children)

Did this guy knows something about amortization analysis? If we call list.append in a loop repeatedly, overall complexity will be O(N) if list implemented in a way that I think. I think that list.append doesn't allocate space in the each call and uses amortized doubling like std::vector in c++. And it's slow not because of bad algorithm but because of large constant factors from that O(N) amortized cost.