Array Time Complexities
Array performance is dominated by direct indexing, linear shifting, and whether the data is sorted enough to support binary search.
The Cost Table
Keep this compact table in your head during interviews:
Operation | Typical cost | Reason Access by index | O(1) | compute the address directly Search unsorted | O(n) | may need to inspect every element Search sorted | O(log n) | binary search halves the remaining range Append or insert at end | amortized O(1) | write at the next free slot, occasional resize Delete at end | amortized O(1) | decrement size, occasional shrink in some implementations Insert at front or middle | O(n) | shift later elements right Delete at front or middle | O(n) | shift later elements left
The table is simple, but it explains many problem constraints. If n is large and the input is unsorted, repeated searching inside a loop is a warning sign for O(n^2).
Access and Search Are Different
Array access means you already know the index. That is O(1). Array search means you know a value or condition and need to find where it occurs. If the array is unsorted, there is no safe shortcut; the target could be anywhere, including the last position.
If the array is sorted, search can become O(log n) with binary search. Sorting is not free, though. Paying O(n log n) upfront only makes sense when it unlocks simpler scanning, many future searches, or a stronger pattern such as two pointers.
End Operations vs Middle Operations
Adding at the end is cheap because it does not disturb existing indices. A dynamic array may occasionally resize, but amortized analysis keeps the long-run append cost at O(1). Removing the last element is also O(1) when no shrinking copy is required.
Adding or removing near the front is different. Every shifted element changes index, so the cost grows with the number of elements after the operation. When a problem suggests repeated front removals from an array, look for a pointer boundary instead of physically deleting.
Use Complexity to Choose Patterns
The most common array optimization is replacing repeated work with remembered structure. A prefix sum remembers cumulative totals. A hash map remembers where values have appeared. Two pointers remember that sorted order eliminates impossible pairs. Sliding windows remember a contiguous region instead of recomputing it from scratch.
Before coding, ask what the expensive operation is. If it is repeated search, add indexing or hashing. If it is repeated range summation, add prefix sums. If it is repeated shifting, keep logical boundaries rather than mutating the array.
Key Takeaways
- Index access is **O(1)**, but searching an unsorted array is **O(n)**.
- Sorted arrays support **O(log n)** binary search but may require an upfront sort.
- Appending at the end is amortized **O(1)** for dynamic arrays; middle changes are **O(n)**.
- Many interview patterns exist to avoid repeated scans, repeated sums, or repeated shifts.