| Algorithm | Worst-case time complexity | Average-case time complexity | Best-case time complexity | Auxiliary space complexity |
|---|---|---|---|---|
| Insertion Sort | Θ(n^2) | Θ(n^2) | O(n) | - |
| BubbleSort | O(n^2) | O(n^2) | O(n) | - |
| MergeSort | Θ(nlogn) | Θ(nlogn) | Θ(nlogn) | - |
| HeapSort | Θ(nlogn) | - | - | - |
| QuickSort | Θ(n^2) | Θ(nlogn) | Θ(nlogn) | - |
| CountingSort | Θ(k + n) | Θ(k + n) | Θ(n) | Θ(n) |
| RadixSort | Θ(d(k + n)) | Θ(d(k + n)) | Θ(n) | - |
| Floyd-Warshall | Θ(V^3) | Θ(V^3) | Θ(V^3) | Θ(V^2) |
| Kruskal | O(|E|log|V|) | - | - | - |
| Prim | O(|E| + |V|log|V| | - | - | - |
| Bellman–Ford | Θ(|E||V|) | - | - | Θ(V) |
| Dijkstra | O(|E| + |V|log|V|) | - | - | - |
| Maximum SubArray | Θ(n) | Θ(n) | Θ(n) | Θ(1) |
| Knuth-Morris-Pratt | Θ(n + m) | Θ(n) | Θ(n) | Θ(n) |
| Rabin-Karp | Θ((n - m + 1)m) | Θ(n) | Θ(n) | - |
| Greatest common divisor (GCD) | - | - | - | - |
| Binary Search | O(nlogn) | O(nlogn) | O(1) | Θ(1) |
| Breadth First Search (BFS) | O(|E|+|V|) | O(|E|+|V|) | - | - |
| Depth First Search (DFS) | O(|E|+|V|) | O(|E|+|V|) | - | - |
| Topological Sort (DFS) | O(|E|+|V|) | O(|E|+|V|) | - | - |
| Longest Increasing Subsequence (LIS) | Θ(n^2) | - | - | Θ(n) |
| Longest Common Subsequence (LCS) | Θ(n^2) | - | - | Θ(n^2) |
| Data Structure | Methods |
|---|---|
| Max Heap | max() - Θ(1), extractMax() - O(nlogn), increaseKey() - O(logn), insert() - O(logn), heapify() - O(logn), heapsort() - O(nlogn) |
| Min Heap | min() - Θ(1), extractMin() - O(nlogn), insert() - O(logn), heapify() - O(logn), heapsort() - O(nlogn) |
| MinMax Heap | min() - Θ(1), max() - Θ(1), extractMin() - O(nlogn), extractMax() - O(nlogn), insert() - O(logn), heapify() - O(logn) |
| Disjoint Set | makeSet() - Θ(1), findSet() - Θ(1), union() - Θ(1) |
| Trie | insert() - O(|s|), search() - O(|s|), searchPrefix() - O(|s|), remove() - O(|s|), size() - O(1) |
| Stack | push() - Θ(1), pop() - Θ(1), empty() - Θ(1), size() - Θ(1), peek() - Θ(1) |
| Queue | enqueue() - Θ(1), dequeue() - Θ(1), empty() - Θ(1), size() - Θ(1) |
| Binary Search Tree | insert() - O(n), search() - O(n), delete() - O(n), contains() - O(n), minimum() - O(n), maximum() - O(n), size() - Θ(1), successor() - O(logn), predecessor() - O(logn), preOrderVisit() - O(n), inOrderVisit() - O(n), postOrderVisit() - O(n) |
| Double Linked List | insertFront() - Θ(1), removeFront() - Θ(1), insertBack() - Θ(1), removeBack() - Θ(1), head() - Θ(1), size() - Θ(1), search() - Θ(n), remove() - Θ(n) |
| Linked List | insertFront() - Θ(1), removeFront() - Θ(1), head() - Θ(1), size() - Θ(1), search() - Θ(n), remove() - Θ(n) |
| Skip List | insert() - Θ(logn), remove() - Θ(logn), search() - O(logn), size() - Θ(1) |
| Graph | buildAdjacencyMatrix() - Θ(|V|^2), buildAdjacencyList() - Θ(|V| + |E|), addEdge() - Θ(1) |
| Red-Black Tree | insert() - O(logn), search() - O(logn), delete() - O(logn), minimum() - O(logn), maximum() - O(logn), successor() - O(logn), predecessor() - O(logn) |
| Interval Tree | insert() - O(logn), search() - O(logn), find() - O(logn), findAll() - O(n), delete() - O(logn), minimum() - O(logn), maximum() - O(logn), successor() - O(logn), predecessor() - O(logn) |
| Segment Tree | build() - O(n), update() - O(logn), search() - O(logn) |
| AVL Tree | insert() - O(logn), search() - O(logn), delete() - O(logn), minimum() - O(logn), maximum() - O(logn), successor() - O(logn) |
| B-Tree | insert() - O(th), search() - O(th), delete() - O(th), successor() - O(th), predecessor() - O(th) |
| QuadTree | insert() - O(logn), search() - O(logn), delete() - O(logn), size() - Θ(1) |
| Fibonacci Heap | insert() - O(1), minimum() - O(1), extractMin() - O(logn), decreaseKey() - O(1), delete() - O(logn) |
| Merkle Tree | build() - O(n), verify() - O(logn), getProofPath() - O(logn) |
| Bloom Filter | search() - O(k), insert() - O(k) |
To add a dependency using Gradle, use the following:
implementation 'com.alexprut:algo:v0.4.0'
To add a dependency using Gradle Kotlin DSL:
implementation("com.alexprut:algo:v0.4.0")
To add a dependency using Maven:
<dependency>
<groupId>com.alexprut</groupId>
<artifactId>algo</artifactId>
<version>v0.4.0</version>
</dependency>
- Gradle 8
- Java 11
./gradlew clean build
./gradlew test
./gradlew goJF
./gradlew verGJF
git-chglog v1.0.0..v2.0.0
Licensed under MIT.