![Algorithm Algorithm](/uploads/1/1/7/8/117802777/717279479.jpeg)
Sorting Algorithms | Space complexity | Time complexity | ||
---|---|---|---|---|
Worst case | Best case | Average case | Worst case | |
Insertion Sort | O(1) | O(n) | O(n2) | O(n2) |
Selection Sort | O(1) | O(n2) | O(n2) | O(n2) |
Smooth Sort | O(1) | O(n) | O(n log n) | O(n log n) |
Bubble Sort | O(1) | O(n) | O(n2) | O(n2) |
Shell Sort | O(1) | O(n) | O(n log n2) | O(n log n2) |
Mergesort | O(n) | O(n log n) | O(n log n) | O(n log n) |
Quicksort | O(log n) | O(n log n) | O(n log n) | O(n log n) |
Heapsort | O(1) | O(n log n) | O(n log n) | O(n log n) |
I would like to see the same type of complexity cheat sheet for algorithms for common math problems: addition, multiplication, division, subtraction, factorization, solving linear systems, solving eigen systems, matrix inversion, etc. Ufo on May 5, 2013. Those depend a lot on the context. Firstly, the complexity for the arithmetic operations. The textbook Algorithms, 4th Edition by Robert Sedgewick and Kevin Wayne surveys the most important algorithms and data structures in use today. Busycal coupon. The broad perspective taken makes it an appropriate introduction to the field. Big-O Algorithm Complexity Cheat Sheet. This webpage covers the space and time Big-O complexities of common algorithms used in Computer Science.
Algorithm Complexity Cheat Sheet Answers
Data Structures | Average Case | Worst Case | ||||
---|---|---|---|---|---|---|
Search | Insert | Delete | Search | Insert | Delete | |
Array | O(n) | N/A | N/A | O(n) | N/A | N/A |
Sorted Array | O(log n) | O(n) | O(n) | O(log n) | O(n) | O(n) |
Linked List | O(n) | O(1) | O(1) | O(n) | O(1) | O(1) |
Doubly Linked List | O(n) | O(1) | O(1) | O(n) | O(1) | O(1) |
Stack | O(n) | O(1) | O(1) | O(n) | O(1) | O(1) |
Hash table | O(1) | O(1) | O(1) | O(n) | O(n) | O(n) |
Binary Search Tree | O(log n) | O(log n) | O(log n) | O(n) | O(n) | O(n) |
B-Tree | O(log n) | O(log n) | O(log n) | O(log n) | O(log n) | O(log n) |
Red-Black tree | O(log n) | O(log n) | O(log n) | O(log n) | O(log n) | O(log n) |
AVL Tree | O(log n) | O(log n) | O(log n) | O(log n) | O(log n) | O(log n) |
n f(n) | log n | n | n log n | n2 | 2n | n! |
---|---|---|---|---|---|---|
10 | 0.003ns | 0.01ns | 0.033ns | 0.1ns | 1ns | 3.65ms |
20 | 0.004ns | 0.02ns | 0.086ns | 0.4ns | 1ms | 77years |
30 | 0.005ns | 0.03ns | 0.147ns | 0.9ns | 1sec | 8.4x1015yrs |
40 | 0.005ns | 0.04ns | 0.213ns | 1.6ns | 18.3min | -- |
50 | 0.006ns | 0.05ns | 0.282ns | 2.5ns | 13days | -- |
100 | 0.07 | 0.1ns | 0.644ns | 0.10ns | 4x1013yrs | -- |
1,000 | 0.010ns | 1.00ns | 9.966ns | 1ms | -- | -- |
10,000 | 0.013ns | 10ns | 130ns | 100ms | -- | -- |
100,000 | 0.017ns | 0.10ms | 1.67ms | 10sec | -- | -- |
1'000,000 | 0.020ns | 1ms | 19.93ms | 16.7min | -- | -- |
10'000,000 | 0.023ns | 0.01sec | 0.23ms | 1.16days | -- | -- |
100'000,000 | 0.027ns | 0.10sec | 2.66sec | 115.7days | -- | -- |
1,000'000,000 | 0.030ns | 1sec | 29.90sec | 31.7 years | -- | -- |
Common Data Structure Operations
Data Structure | Time Complexity | Space Complexity | |||||||
---|---|---|---|---|---|---|---|---|---|
Average | Worst | Worst | |||||||
Access | Search | Insertion | Deletion | Access | Search | Insertion | Deletion | ||
Array | Θ(1) | Θ(n) | Θ(n) | Θ(n) | O(1) | O(n) | O(n) | O(n) | O(n) |
Stack | Θ(n) | Θ(n) | Θ(1) | Θ(1) | O(n) | O(n) | O(1) | O(1) | O(n) |
Queue | Θ(n) | Θ(n) | Θ(1) | Θ(1) | O(n) | O(n) | O(1) | O(1) | O(n) |
Singly-Linked List | Θ(n) | Θ(n) | Θ(1) | Θ(1) | O(n) | O(n) | O(1) | O(1) | O(n) |
Doubly-Linked List | Θ(n) | Θ(n) | Θ(1) | Θ(1) | O(n) | O(n) | O(1) | O(1) | O(n) |
Skip List | Θ(log(n)) | Θ(log(n)) | Θ(log(n)) | Θ(log(n)) | O(n) | O(n) | O(n) | O(n) | O(n log(n)) |
Hash Table | N/A | Θ(1) | Θ(1) | Θ(1) | N/A | O(n) | O(n) | O(n) | O(n) |
Binary Search Tree | Θ(log(n)) | Θ(log(n)) | Θ(log(n)) | Θ(log(n)) | O(n) | O(n) | O(n) | O(n) | O(n) |
Cartesian Tree | N/A | Θ(log(n)) | Θ(log(n)) | Θ(log(n)) | N/A | O(n) | O(n) | O(n) | O(n) |
B-Tree | Θ(log(n)) | Θ(log(n)) | Θ(log(n)) | Θ(log(n)) | O(log(n)) | O(log(n)) | O(log(n)) | O(log(n)) | O(n) |
Red-Black Tree | Θ(log(n)) | Θ(log(n)) | Θ(log(n)) | Θ(log(n)) | O(log(n)) | O(log(n)) | O(log(n)) | O(log(n)) | O(n) |
Splay Tree | N/A | Θ(log(n)) | Θ(log(n)) | Θ(log(n)) | N/A | O(log(n)) | O(log(n)) | O(log(n)) | O(n) |
AVL Tree | Θ(log(n)) | Θ(log(n)) | Θ(log(n)) | Θ(log(n)) | O(log(n)) | O(log(n)) | O(log(n)) | O(log(n)) | O(n) |
KD Tree | Θ(log(n)) | Θ(log(n)) | Θ(log(n)) | Θ(log(n)) | O(n) | O(n) | O(n) | O(n) | O(n) |
Algorithm Time Complexity Cheat Sheet
Array Sorting Algorithms
Know Thy Complexities
Algorithm | Time Complexity | Space Complexity | ||
---|---|---|---|---|
Best | Average | Worst | Worst | |
Quicksort | Ω(n log(n)) | Θ(n log(n)) | O(n^2) | O(log(n)) |
Mergesort | Ω(n log(n)) | Θ(n log(n)) | O(n log(n)) | O(n) |
Timsort | Ω(n) | Θ(n log(n)) | O(n log(n)) | O(n) |
Heapsort | Ω(n log(n)) | Θ(n log(n)) | O(n log(n)) | O(1) |
Bubble Sort | Ω(n) | Θ(n^2) | O(n^2) | O(1) |
Insertion Sort | Ω(n) | Θ(n^2) | O(n^2) | O(1) |
Selection Sort | Ω(n^2) | Θ(n^2) | O(n^2) | O(1) |
Tree Sort | Ω(n log(n)) | Θ(n log(n)) | O(n^2) | O(n) |
Shell Sort | Ω(n log(n)) | Θ(n(log(n))^2) | O(n(log(n))^2) | O(1) |
Bucket Sort | Ω(n+k) | Θ(n+k) | O(n^2) | O(n) |
Radix Sort | Ω(nk) | Θ(nk) | O(nk) | O(n+k) |
Counting Sort | Ω(n+k) | Θ(n+k) | O(n+k) | O(k) |
Cubesort | Ω(n) | Θ(n log(n)) | O(n log(n)) | O(n) |