Skip to content

Latest commit

 

History

History
30 lines (23 loc) · 1.95 KB

README.md

File metadata and controls

30 lines (23 loc) · 1.95 KB

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)