Quick Overview
A dynamic array doubles rather than growing by one, so the expensive copy lands on the 1st, 2nd, 4th and 8th push. Averaged across every push, that is `O(1)` amortised.
A static array reserves a fixed block of sequential memory addresses at allocation time. A Dynamic Array (like JavaScript Arrays or Python Lists) expands automatically as new elements are added.
When a dynamic array reaches maximum capacity, it cannot simply expand in-place because adjacent memory might be occupied. Instead:
2 × Capacity).N elements into the new block.Initial Capacity [4]: [ 10 | 20 | 30 | 40 ] (FULL)
│
Doubling Allocation (Capacity 8)
▼
New Block: [ 10 | 20 | 30 | 40 | 50 | __ | __ | __ ]
▲──────────────▲ ▲
Copied Items New Item
Copying N elements takes O(N) time, but resizing happens rarely (only after 1, 2, 4, 8, 16, ... elements). Averaged across N insertions, the cost per push operation is O(1) amortized.
| Operation | Time Complexity | Note |
|---|---|---|
Index Access arr[i] | O(1) | Direct pointer arithmetic calculation |
| Append / Push | O(1) Amortized | Occasional O(N) reallocation |
| Insert / Remove at Start | O(N) | Requires shifting all N elements right or left |
arr.unshift() or arr.shift() in a loop turns an O(N) algorithm into an accidental O(N^2) bottleneck because every shift re-indexes all elements. Use two pointers or queues instead.Understand array memory layouts to avoid hidden re-indexing costs. Next, let's explore the Two Pointers Pattern!
Big O describes how work grows, not how long it takes. An `O(N^2)` algorithm on 1,000 items does a million steps; the same work at `O(N log N)` does about 10,000.
A nested loop tests every pair in `O(N^2)`. On sorted data, moving two pointers inward from both ends rules out half the remaining candidates at each step and settles it in one `O(N)` pass.
Two pointers moving at different speeds must eventually meet inside a loop, the way a faster runner laps a slower one. That detects a cycle in `O(N)` time and `O(1)` space, with no visited set.