Skip to content
CodeWiki
Practice
Paths
Tracks
Cheatsheets
Playground
Glossary
AI era
Search
⌘K
English
English
Chinese
Practice
Paths
Tracks
Cheatsheets
Playground
Glossary
AI era
English
English
Chinese
Practice
/
Quiz
/
CS foundations
/
Algorithmic complexity
Why can append to a geometrically growing dynamic array be amortized O(1) even though one…
from Algorithmic complexity
Node 24
intermediate
1 min
Why can append to a geometrically growing dynamic array be amortized O(1) even though one append may be O(n)?
Resizing never copies existing elements.
The total copying across n appends is O(n), so it spreads to O(1) per append.
Average-case and amortized analysis mean the same thing.
The array reserves infinite memory on its first append.
Check
Ask AI about this kata
Report an error
next kata
A function performs 4n² + 20n + 300 modeled operations. What is its tight asymptotic time…
Quiz
A new version is available
Reload