This repository has the objective of presenting examples of data structure, search algorithms, sorting algorithms, and their respective complexities in the worst case.
For most of the code I also developed the unit tests, you can find them by accessing the root of the solution and /test.
This repository is under construction so some algorithms mentioned in the tables may be missing from the solution
For data structure, we only look at worst-case time complexity.
| Data Structures | Insertion | Remove | Search | Access |
|---|---|---|---|---|
| Array | O(n) | O(n) | O(n) | O(1) |
| Doubly-Linked List | O(1) | O(1) or O(n) | O(n) | O(n) |
| Circular-Linked List | O(1) | O(1) or O(n) | O(n) | O(n) |
| Singly-Linked List | O(n) | O(n) | O(n) | O(n) |
| Hash Map | O(n) | O(n) | O(n) | O(n) |
| Min Heap | O(log(n)) | O(log(n)) | O(n) | |
| AVL | O(log(n)) | O(log(n)) | O(log(n)) | |
| Binary Search Tree | O(n) | O(n) | O(n) |
| Algorithm | Best | Average | Wrost |
|---|---|---|---|
| Quick Sort | O(n*log(n)) | O(n*log(n)) | O(n^2) |
| Mergesort | O(n*log(n)) | O(n*log(n)) | O(n*log(n)) |
| Heapsort | O(n*log(n)) | O(n*log(n)) | O(n*log(n)) |
| Bubble Sort | O(n) | O(n^2) | O(n^2) |
| Insertion Sort | O(n) | O(n^2) | O(n^2) |
| Selection Sort | O(n^2) | O(n^2) | O(n^2) |
| Radix Sort | O(n+k) | O(n+k) | O(n+k) |
| Counting Sort | O(n+k) | O(n+k) | O(n+k) |
| Algorithm | Best | Average | Wrost |
|---|---|---|---|
| Linear(Array) | O(1) | O(n) | O(n) |
| Binary Search | O(1) | O(Log(n)) | O(Log(n)) |
| Binary Search Tree | O(log(n)) | O(n) | O(n) |
| Breadth-First Search | O(V+E) | ||
| Depth-First Search | O(V+E) | ||
| A* | O(E) | ||
| Predictive Search | |||
| Interpolation Search | O(log(log(n)) | O(log(log(n)) | O(n) |
| Fibonacci Search | O(1) | O(log(n)) | O(log(n)) |
| Kruskal's Algorithm | |||
| Prim's Algorithm | O(v^2) | O(v^2) | O(v^2) |
| Dijkstra's Algorithm | O(v^2) | O(v^2) | O(v^2) |