Hello 👋
I’m Liangqin, a Ph.d. student at the University of Kansas. This site documents my solutions for algorithm questions.
I try to give different solutions with different time and space complexity. I think a better solution should be clear, simple, easy to understand, rather than SHORT!
🥳 CodingInterviews(剑指 Offer II): 73. Done
Complexity 💬
Common operations and sorting algorithms, at a glance. n is the number of elements.
Slower growth
O(1)
O(log n)
O(n)
O(n log n)
O(n2)
Faster growth
Data structures
14 structuresOperation costs and total storage. † denotes an amortized bound; — means not applicable.
Average / expected
| Structure | Access | Search | Insert | Delete | Storage |
|---|---|---|---|---|---|
| Array | O(1) | O(n) | O(n) | O(n) | O(n) |
| Stack | O(n) | O(n) | O(1) | O(1) | O(n) |
| Queue | O(n) | O(n) | O(1) | O(1) | O(n) |
| Singly-linked list | O(n) | O(n) | O(1) | O(1) | O(n) |
| Doubly-linked list | O(n) | O(n) | O(1) | O(1) | O(n) |
| Skip list | O(log n) | O(log n) | O(log n) | O(log n) | O(n) |
| Hash table | — | O(1) | O(1) | O(1) | O(n) |
| Binary search tree | O(log n) | O(log n) | O(log n) | O(log n) | O(n) |
| Treap / Cartesian tree | — | O(log n) | O(log n) | O(log n) | O(n) |
| B-tree | O(log n) | O(log n) | O(log n) | O(log n) | O(n) |
| Red-black tree | O(log n) | O(log n) | O(log n) | O(log n) | O(n) |
| Splay tree † | — | O(log n) | O(log n) | O(log n) | O(n) |
| AVL tree | O(log n) | O(log n) | O(log n) | O(log n) | O(n) |
| KD tree | O(log n) | O(log n) | O(log n) | Varies | O(n) |
Compare worst-case costs
| Structure | Access | Search | Insert | Delete | Storage |
|---|---|---|---|---|---|
| Array | O(1) | O(n) | O(n) | O(n) | O(n) |
| Stack | O(n) | O(n) | O(1) | O(1) | O(n) |
| Queue | O(n) | O(n) | O(1) | O(1) | O(n) |
| Singly-linked list | O(n) | O(n) | O(1) | O(1) | O(n) |
| Doubly-linked list | O(n) | O(n) | O(1) | O(1) | O(n) |
| Skip list | O(n) | O(n) | O(n) | O(n) | O(n log n) |
| Hash table | — | O(n) | O(n) | O(n) | O(n) |
| Binary search tree | O(n) | O(n) | O(n) | O(n) | O(n) |
| Treap / Cartesian tree | — | O(n) | O(n) | O(n) | O(n) |
| B-tree | O(log n) | O(log n) | O(log n) | O(log n) | O(n) |
| Red-black tree | O(log n) | O(log n) | O(log n) | O(log n) | O(n) |
| Splay tree † | — | O(n) | O(n) | O(n) | O(n) |
| AVL tree | O(log n) | O(log n) | O(log n) | O(log n) | O(n) |
| KD tree | O(n) | O(n) | O(n) | O(n) | O(n) |
Operation assumptions
- Arrays are unsorted; inserting or deleting can shift elements. Stack and queue access means an arbitrary element; reading the top or front is O(1).
- Linked-list insertion and deletion assume the necessary node references are already known, including the predecessor for a singly-linked list.
- Skip lists and treaps use randomized bounds. Skip-list storage is O(n) in expectation; with O(log n) levels allowed, the worst case is O(n log n).
- † Splay-tree costs are O(log n) amortized; one operation can take O(n). A treap is a Cartesian tree with randomized priorities.
- KD-tree lookup and insertion assume a balanced tree and fixed dimension. Deletion depends on dimension and implementation; nearest-neighbor and range queries have different bounds.
Sorting algorithms
13 algorithmsTime by input case. Auxiliary space excludes the input array and includes temporary buffers and recursion.
| Algorithm | Best time | Average time | Worst time | Aux. space worst case |
|---|---|---|---|---|
| Quicksort | O(n log n) | O(n log n) | O(n2) | O(n) |
| Mergesort | O(n log n) | O(n log n) | O(n log n) | O(n) |
| Timsort | O(n) | O(n log n) | O(n log n) | O(n) |
| Heapsort | O(n log n) | O(n log n) | O(n log n) | O(1) |
| Bubble sort | O(n) | O(n2) | O(n2) | O(1) |
| Insertion sort | O(n) | O(n2) | O(n2) | O(1) |
| Selection sort | O(n2) | O(n2) | O(n2) | O(1) |
| Tree sort | O(n log n) | O(n log n) | O(n2) | O(n) |
| Shell sort | Gap-dependent | Gap-dependent | Gap-dependent | O(1) |
| Bucket sort | O(n + K) | O(n + K) | O(n2) | O(n + K) |
| Radix sort | O(d(n + b)) | O(d(n + b)) | O(d(n + b)) | O(n + b) |
| Counting sort | O(n + K) | O(n + K) | O(n + K) | O(n + K) |
| Cubesort | O(n) | O(n log n) | O(n log n) | O(n) |
K = key range or bucket count · d = digits processed · b = radix / digit range
Implementation assumptions
- Quicksort uses the usual recursive implementation: O(n) worst-case stack space. Recursing on the smaller partition and looping over the larger one limits the stack to O(log n).
- Bubble sort stops early when a pass makes no swaps. The heapsort best-case bound assumes distinct keys. Tree sort uses an unbalanced binary search tree; Shell sort depends on its gap sequence.
- Bucket sort assumes uniformly distributed keys and K proportional to n for its average bound. Radix sort uses a stable counting pass per digit.
- Counting sort uses a stable output buffer, giving O(n + K) auxiliary space. Rewriting the input from counts can use O(K) space when stability is not required.