notesonly.in

Dynamic array push: most pushes cost O(1), but when full, resizing copies n elements: O(n). Over n pushes starting from size 1, total copies = 1+2+4+...+n/2 < 2n, so total O(n) and amortized O(1) per push. The rare expensive operation is paid for by many cheap ones.