algorithms-data-structures

# Algorithms & Data Structures An algorithm is a finite, unambiguous sequence of well-defined instructions for solving a class of problems. A data structure is an organization of data that enables efficient access and modification. Together they form the mechanical foundation of all computation. This skill catalogs the canonical algorithms and data structures with complexity analysis, implementation notes, and selection heuristics. **Agent affinity:** knuth (algorithm analysis, literate implementation), turing (computability, theoretical limits) **Concept IDs:** code-sorting-algorithms, code-searching-algorithms, code-big-o-notation, code-dynamic-programming ## Complexity Analysis at a Glance Before studying individual algorithms, internalize the complexity hierarchy. Every algorithm has a time cost and a space cost, each expressed as a function of input size n. | Class | Name | Example | |---|---|---| | O(1) | Constant | Array index access, hash table lookup (average) | | O(log n) | Logarithmic | Binary search, balanced BST lookup | | O(n) | Linear | Linear search, single traversal | | O(n log n) | Linearithmic | Merge sort, heap sort, efficient comparison sorts | | O(n^2) | Quadratic | Bubble sort, insertion sort (worst), naive string matching | | O(n^3) | Cubic | Naive matrix multiplication, Floyd-Warshall | | O(2^n) | Exponential | Brute-force subset enumeration, naive recursive Fibonacci | | O(n!) | Factorial | Brute-force permutation, naive TSP | **Big-O** gives ...