Compare the performance characteristics of common operations (random access, append, insert/remove in the middle, contains) for arrays and ArrayList. What does ArrayList's add() being 'amortized O(1)' mean?

## Big-O in one sentence **Big-O notation** describes how an operation's cost grows with the number of elements n. **O(1)** = constant time (independent of n); **O(n)** = linear (proportional to n). We use it to compare operations without measuring exact nanoseconds. Because an `ArrayList` is **backed by an array**, most of its costs mirror an array's. Let's go operation by operation. ## Random access by index — O(1) for both Reading or writing `arr[i]` or `list.get(i)` / `list.set(i, v)` is **constant time**. An array is a contiguous block, so the address of element i is just `base + i * elementSize` — one arithmetic step, no scanning. ArrayList just forwards to its internal array. This is arrays' superpower and why they (and ArrayList) crush a LinkedList, where `get(i)` must walk i nodes (O(n)). ## Appending at the end A raw array has **no append** — its size is fixed. To "grow" it you manually allocate a bigger array and copy (O(n)). ArrayList's `add(e)` (append at end) is **amortized O(1)** — explained below. Most of the time it's a single write to the next free slot. Occasionally it must resize. ### What 'amortized O(1)' means When ArrayList's internal array is **full**, the next `add()` must: 1. allocate a new array about **1.5x** the current capacity, 2. **copy** all existing elements into it (O(n)), 3. then store the new element. That one add is expensive (O(n)). But resizing happens **rarely** — only when capacity is exhausted — and each resize roughly doubles headroom, so the number of resizes grows only logarithmically. If you spread (amortize) the total cost of all those occasional O(n) copies across the many cheap O(1) adds, the **average cost per add is still constant**. That averaged guarantee is what "**amortized O(1)**" means: any single add *might* be O(n), but a long run of adds costs O(1) each on average. (Pre-sizing with `new ArrayList<>(expectedSize)` avoids the resizes entirely.) ## Insert or remove in the middle — O(n) for both To insert at index i (or remove it), every element after i must **shift** one slot over to keep the block contiguous. That shift is done with `System.arraycopy` and touches up to n elements, so it's **O(n)**. This is true for a raw array too (you'd shift manually). Removing the **last** element is O(1) (no shift); removing the **first** is the worst case (shift everything). If your workload is dominated by middle inserts/removes, an `ArrayList` is a poor fit — a `LinkedList` does O(1) insert/remove *once you have the node*, though finding the position is still O(n), and an `ArrayDeque` is better for head/tail churn. ## Search by value (contains / indexOf) — O(n) Neither structure indexes by value, so `contains(x)` / `indexOf(x)` scans linearly until it finds a match — **O(n)**. If you frequently test membership, use a **HashSet** (O(1) average contains) instead of a List/array. ## Summary table | Operation | Array | ArrayList | |---|---|---| | get/set by index | O(1) | O(1) | | append at end | n/a (fixed) | amortized O(1) | | insert/remove middle | O(n) | O(n) | | remove last | O(1) | O(1) | | contains / indexOf | O(n) | O(n) | ## Practical guidance - Index- and append-heavy, iterate-a-lot workloads → **ArrayList** (or array for fixed primitives) is ideal; pre-size it when you know the count. - Heavy head insert/remove → **ArrayDeque** / **LinkedList**. - Frequent membership checks → **HashSet**. Measure before optimizing; for small n the constant factors dominate and ArrayList's cache-friendly contiguous layout usually beats 'theoretically faster' linked structures.