- insertion sort
- selection sort
- bubble sort
- heap sort
- Quick Sort - in place
- Merge Sort
- Binary Search
Vignesh S. Trevahok
Trevahok
/ dsa checklist.md
Last active
December 19, 2023 14:17
a checklist for data structures and algorithms
Trevahok
/ stl containers and time complexity.md
Last active
July 31, 2020 04:56
| Function | Creation | Insertion | Updation | Deletion | Search | Notes |
|---|---|---|---|---|---|---|
| vector | O(n) | O(1) | O(1) | O(n) | O(n) | Insertion and deletion inbetween is heavy, push_back and pop_back is amortized to O(1) |
| deque | O(1) | O(1) | O(1) | O(1) | O(n) | Insertion nad deletion is possible at both ends of the list |
| stack | O(1) | O(1) | NA | O(1) | O(n) | Insertion and deletion is possible only at the top |
| queue | O(1) | O(1) | NA | O(1) | O(n) | Insertion at back and deletion at front |
| unordered_map | O(1) | O(1) | O(1) | O(1) | O(1) | Can't store duplicates |
| unordered_set | O(1) | O(1) | O(1) | O(1) | O(1) | Can't store duplicates |
| priority_queue | O(1) | O(logn) | NA | O(logn) | O(nlogn) | Random access is not possible |
| map | O(1) | O(logn) | O(logn) | O(logn) | O(logn) | No duplicates and slower than unordered_map |
Trevahok
/ STLfunctions and their time complexity.md
Last active
July 25, 2020 11:44
| STL function | Time Complexity | Space complexity |
|---|---|---|
| sort() | O(nlogn) | O(1) |
| lower_bound() | O( logn) | O(1) |
| upper_bound() | O(logn) | O(1) |
| next_permutation() | O(n) | O(1) |
| prev_permutation() | O(n) | O(1) |
| partial_sort( , k ) | O(n +klogk) | O(1) |
| nth_element() | O(n) | O(1) |
| Operation | Code |
|---|---|
| To remove last set bit | x & ( x - 1 ) |
| To double | x <<= 1 |
| To halve | x >>= 1 |
| To lowercase | x | ‘ ‘ |
| To togglecase | x ^ ‘ ‘ |
| Is power of two? | x && !(x & (x-1) ) |
| log base 2 ( brian kern algorithm) | int res = 0; while (x >>= 1) res++; return res; |
| multiply by 7 | ( (x<<3) - x ) |