Data Structures & Algorithms
This repository serves as an implementation of the various data structures and algorithms that I am studying in my undergrad studies of Computer Science Engineering. I am trying to implement them in 3 languages(C/C++, Python, Java).
Programmers willing to contribute or add more language efficiencies are most welcome to send pull requests.
IMPORTANT
- Always specify the Problem statement in a comment at the top of the program.
- You can also give link to a webpage where the problem statement or tutorial of that particular program is present.
Space and Time Complexities of Various Algorithms
| Algorithms | Best Case Time Complexity | Average Case Time Complexity | Worst Case Time Complexity | Worst Case Space Complexity |
|---|---|---|---|---|
| Linear Search | Ω(1) | Θ(n) | O(n) | O(1) |
| Binary Search | Ω(1) | Θ(log(n)) | O(log(n)) | O(1) |
| Selection Sort | Ω(n^2) | Θ(n^2) | O(n^2) | O(1) |
| Bubble Sort | Ω(n) | Θ(n^2) | O(n^2) | O(1) |
| Insertion Sort | Ω(n) | Θ(n^2) | O(n^2) | O(1) |
| Merge Sort | Ω(n log(n)) | Ω(n log(n)) | O(n log(n)) | O(n) |
| Quick Sort | Ω(n log(n)) | Θ(n log(n)) | O(n^2) | O(log(n)) |
| Counting Sort | Ω(n+k) | Θ(n+k) | O(n+k) | O(k) |
| Radix sort | Ω(nk) | Θ(nk) | O(nk) | O(n+k) |
| Heap Sort | Ω(n log(n)) | Θ(n log(n)) | O(n log(n)) | O(1) |
| Tree Sort | Ω(n log(n)) | Ω(n log(n)) | O(n^2) | O(n) |
| Bucket sort | Ω(n+k) | Ω(n+k) | O(n^2) | O(n) |
| Cube Sort | Ω(n) | Θ(n log(n)) | O(n log(n)) | O(n) |
| Tim Sort | Ω(n) | Ω(n log(n)) | O(n log(n)) | O(n) |