Tools
Complexity lookup
Type an operation or algorithm to see its best, average, and worst case in one place, with the assumption behind the average case and the caveat people usually miss.
- Array index (read or write)Arrays
- Dynamic array appendArrays
- Dynamic array insert or delete in the middleArrays
- Linear searchSearching
- Binary searchSearching
- Hash table lookup, insert, deleteHash tables
- Linked list insert or delete at a known nodeLinked lists
- Linked list searchLinked lists
Array index (read or write)
| Best case | O(1) |
|---|---|
| Average case | O(1) |
| Worst case | O(1) |
| Auxiliary space | O(1) |
Assumptions: Random access into contiguous memory.
Watch out for: Linked lists have no O(1) index. Reaching position k takes O(k).