Big-O Reference
Complexity for the structures and algorithms you actually use, with what each costs at a real n.
| Structure | Access | Search | Insert | Delete | Space |
|---|---|---|---|---|---|
| Array Indexing is free; inserting in the middle shifts everything after it. | O(1) | O(n) | O(n) | O(n) | O(n) |
| Dynamic array Append is amortised O(1) — most are free, and the occasional resize copies everything. | O(1) | O(n) | O(1) | O(n) | O(n) |
| Linked list Insert and remove are constant only once you already hold the node. Finding it is the O(n) part. | O(n) | O(n) | O(1) | O(1) | O(n) |
| Hash table Constant on average. Worst case is O(n) when every key collides, which is why hash quality matters. | O(1) | O(1) | O(1) | O(1) | O(n) |
| Binary search tree Only while balanced. Insert sorted data into a plain BST and every operation degrades to O(n). | O(log n) | O(log n) | O(log n) | O(log n) | O(n) |
| Balanced tree (AVL, red-black) Pays a rebalance on write to guarantee the height, so the log is a guarantee rather than a hope. | O(log n) | O(log n) | O(log n) | O(log n) | O(n) |
| Binary heap Only the minimum or maximum is cheap to reach — which is exactly what a priority queue needs. | O(n) | O(n) | O(log n) | O(log n) | O(n) |
| B-tree Wide and shallow, so each node is one disk or page read. This is what your database index is. | O(log n) | O(log n) | O(log n) | O(log n) | O(n) |
About
Big-O describes how cost grows with input size, not how fast something runs — which is why the constant factors it ignores still decide real performance.