A compact reference for the algorithms and data structures implemented in this repository. Each entry links to its implementation and tests; the service layer exposes the public operations through MCP and HTTP.
Algorithm
Definition
Complexity
Implementation
Quicksort
Partitions an array around a pivot and recursively sorts the two sides.
Average $O(n \log n)$ ; worst $O(n^2)$ ; $O(\log n)$ average stack space.
Source · Tests
Merge Sort
Divides an array, sorts each half, and merges the sorted halves.
$O(n \log n)$ time; $O(n)$ space; stable.
Source · Tests
Heap Sort
Builds a max-heap and repeatedly moves its maximum to the sorted suffix.
$O(n \log n)$ time; $O(1)$ auxiliary space.
Source · Tests
Algorithm
Definition
Complexity
Implementation
Binary Search
Repeatedly halves a sorted search interval to locate a target.
$O(\log n)$ time; $O(1)$ space. Requires sorted input.
Source · Tests
Knuth-Morris-Pratt
Finds a pattern by reusing an LPS prefix table after mismatches.
$O(n + m)$ time; $O(m)$ space.
Source · Tests
Valid Parentheses
Uses a stack to verify that opening and closing brackets are properly nested.
$O(n)$ time; $O(n)$ space. Non-bracket characters are ignored.
Source · Tests
Algorithm
Definition
Complexity
Implementation
Dijkstra
Relaxes non-negative weighted edges using a priority queue to find shortest paths.
$O((V + E) \log V)$ time with a binary heap.
Source · Tests
Bellman-Ford
Repeatedly relaxes every edge to support negative weights and detect negative cycles.
$O(VE)$ time; $O(V)$ space.
Source · Tests
A*
Combines path cost with a heuristic estimate to guide shortest-path exploration.
$O((V + E) \log V)$ typical priority-queue bound.
Source · Tests
Topological Sort
Removes zero-in-degree vertices in BFS order to produce a dependency ordering.
$O(V + E)$ time; $O(V)$ space. Requires a DAG.
Source · Tests
Breadth-First Search
Explores an unweighted graph level by level from a source vertex.
$O(V + E)$ time; $O(V)$ space.
Source · Tests
Depth-First Search
Explores as far as possible along each branch before backtracking.
$O(V + E)$ time; $O(V)$ space.
Source · Tests
Kruskal
Sorts weighted undirected edges and joins components without creating cycles.
$O(E \log E)$ time; $O(V + E)$ space.
Source · Tests
Structure
Definition
Typical operation complexity
Implementation
Binary Search Tree
Stores ordered keys in recursively partitioned left and right subtrees.
Average search/insert $O(\log n)$ ; worst $O(n)$ .
Source · Tests
AVL Tree
Maintains a BST balance invariant through rotations after updates.
Search/insert/delete $O(\log n)$ .
Source · Tests
Trie
Stores strings character by character for exact lookup and prefix queries.
Insert/search $O(L)$ for word length $L$ ; autocomplete depends on results.
Source · Tests
Union-Find
Tracks disjoint sets with representative lookup and component merging.
Near-constant amortized operations, $O(\alpha(n))$ .
Source · Tests
Singly Linked List
Connects values through forward-only node pointers.
Append/prepend $O(1)$ ; search/delete/reverse $O(n)$ .
Source · Tests
Algorithm
Definition
Complexity
Implementation
0/1 Knapsack
Selects each item at most once to maximize value under a capacity limit.
$O(nC)$ time and space for $n$ items and capacity $C$ .
Source · Tests
Longest Common Subsequence
Builds a table to find the longest ordered sequence shared by two inputs.
$O(nm)$ time and space.
Source · Tests
Numeric, Compression, and Machine Learning
Algorithm
Definition
Complexity
Implementation
Euclidean Algorithm
Repeatedly replaces a pair with the divisor and remainder to find their GCD.
$O(\log \min(
a
Sieve of Eratosthenes
Marks composite multiples to enumerate all primes up to a limit.
$O(n \log \log n)$ time; $O(n)$ space.
Source · Tests
Huffman Coding
Greedily merges the least-frequent symbols into an optimal prefix-code tree.
$O(n + k \log k)$ construction time for $n$ symbols and $k$ distinct characters.
Source · Tests
K-Means
Iteratively assigns points to the nearest centroid and recomputes centroids.
$O(i k n d)$ for iterations $i$ , clusters $k$ , samples $n$ , and dimensions $d$ .
Source · Tests
Principal Component Analysis
Projects centered data onto directions of greatest covariance.
Dominated by covariance/eigendecomposition cost; depends on samples and dimensions.
Source · Tests
Choosing an Implementation Use the linked source and tests as the executable reference. The roadmap tracks planned work, while the ADR index records the major implementation choices. Service consumers can use the stateless MCP server or HTTP API .