- Big O Notation Cheat Sheet Pdf
- Big O Notation Chart
Sorting Algorithms| 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) |
Big O notation is useful when analyzing algorithms for efficiency. For example, the time (or the number of steps) it takes to complete a problem of size n might be found to be T(n) = 4n 2 − 2n + 2.As n grows large, the n 2 term will come to dominate, so that all other terms can be neglected—for instance when n = 500, the term 4n 2 is 1000 times as large as the 2n term. Big o cheatsheet with complexities chart Big o complete Graph!Bigo graph1 Legend!legend3!Big o cheatsheet2!DS chart4!Searching chart5 Sorting Algorithms chart!sorting chart6!Heaps chart7!graphs chart8. HackerEarth is a global.
Data Structures Comparison| 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) |
Big-O Notation Cheat Sheet This cheat sheet shows the Big-O time and space complexities (runtime analysis) of common algorithms used in the computer science field. You can see which collection type or sorting algorithm to use at a glance to write the most efficient code. Big-O Cheat Sheet; Big-O Cheat Sheet. Sorting algorithms are a fundamental part of computer science. Being able to sort through a large data set quickly and efficiently is a problem you will be likely to encounter on nearly a daily basis. Here are the main sorting algorithms.
Growth Rates| 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) |
Big O Notation Cheat Sheet Pdf
Array Sorting Algorithms
Big O Notation Chart
| 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) |