Post #1513603
2026-04-21 15:39 UTC
Expanding a dynamic array to powers of 2 has amortized constant complexity so filling one up from empty is O(n).
Replies (1)
-
@FishFace@piefed.social 2026-04-21 16:34
Well I just had to work it out again myself and you’re right. I dunno what scenario I was thinking of that had worse complexity and whether it was really due to dynamic arrays; I just remember getting asked about it in some interview and somehow the answer ended up being “use a linked list and the time complexity goes down to linear” /shrug Thanks for the correction!