Implement a dynamic array (vector)

Problem Implement a dynamic array (vector) from scratch with working code: indexed get/set, append with automatic resizing, and complexity analysis.

Requirements

• API: get(i)/set(i, v) with bounds checking, add(v) (append), size(), optionally insert(i, v)/removeAt(i).
• Backing fixed-size array; grow when full by allocating a larger array and copying.

Core design

• Fields: elements[] (capacity), size. add: if size == capacity → resize(capacity * 2), then elements[size++] = v. Growth factor 2 (or 1.5) — geometric growth is what makes append amortized O(1); linear growth (+k) degrades to O(n) amortized. Bounds-check against size, not capacity (the classic bug).

Discussion points

• Amortized analysis: total copy cost over n appends with doubling is < 2n → O(1) amortized; explain via the aggregate or accounting argument — this is the core of the question.
• Complexities: get/set O(1); append O(1) amortized / O(n) worst; insert/remove at index O(n) shifts.
• Extras that score: shrink policy on removal (halve at 1/4 full — and why 1/4, not 1/2: hysteresis against thrashing), why Java's ArrayList grows at 1.5x (allocator reuse), generics/object cleanup on remove, thread-unsafety.