Algorithms

Back

By Category

Sorting & Selection

• Bubble Sort - O(n²), simple, educational
• Counting Sort - O(n + k), linear for integers
• Heap Sort - O(n log n), guaranteed, in-place
• Merge Sort - O(n log n), stable, divide and conquer
• Quick Sort - O(n log n), average, divide and conquer
• Quickselect - O(n), average, k-th element selection
• Radix Sort - O(d(n + k)), linear for fixed digits

Searching

• Binary Search - O(log n), sorted arrays
• Sliding Window - O(n), contiguous subarray problems
• Two Pointers - O(n), linear traversal patterns

Graph Algorithms

• A* Search - O(b^d), heuristic pathfinding
• Bellman-Ford - O(VE), handles negative weights
• Breadth-First Search (BFS) - O(V + E), shortest path unweighted
• Depth-First Search (DFS) - O(V + E), traversal and cycle detection
• Dijkstra - O(E log V), shortest path weighted
• Floyd-Warshall - O(V³), all-pairs shortest path
• Minimum Spanning Tree (Kruskal/Prim) - O(E log E), connects all vertices with minimum cost
• Topological Sort - O(V + E), DAG ordering

Dynamic Programming

• Edit Distance (Levenshtein) - O(mn), string similarity
• Knapsack - O(nW), subset selection optimization
• Longest Common Subsequence (LCS) - O(mn), find shared subsequence
• Longest Increasing Subsequence (LIS) - O(n log n), find increasing sequence
• Matrix Dynamic Programming - O(mn), grid-based problems

String Algorithms

• Knuth-Morris-Pratt (KMP) - O(n + m), pattern matching
• Rabin-Karp - O(n + m), avg, rolling hash
• Z-Algorithm - O(n), prefix matching

Greedy Algorithms

• Activity Selection - O(n log n), maximum activities
• Huffman Coding - O(n log n), optimal prefix codes
• Interval Scheduling - O(n log n), non-overlapping intervals

Backtracking

• N-Queens - O(n!), constraint satisfaction
• Permutations - O(n × n!), all arrangements
• Subsets - O(n × 2^n), power set generation

Bit Manipulation & Math

• Bitmask Dynamic Programming - O(n² × 2^n), subset state DP
• Fast Exponentiation - O(log n), power computation
• Greatest Common Divisor (GCD) - O(log n), Euclidean algorithm
• Sieve of Eratosthenes - O(n log log n), prime generation
• XOR Tricks - O(n), duplicate/missing detection

Streaming Algorithms

• Count-Min Sketch - O(1), frequency estimation
• HyperLogLog - O(1), cardinality estimation
• Reservoir Sampling - O(n), random sampling from stream

Cryptography

• ROT13 - O(n), simple substitution cipher

---

Complexity Reference

Time Complexity Classes

Class	Name	Example
O(1)	Constant	Hash table lookup
O(log n)	Logarithmic	Binary search
O(n)	Linear	Array scan
O(n log n)	Linearithmic	Merge sort
O(n²)	Quadratic	Nested loops
O(2^n)	Exponential	Subset enumeration
O(n!)	Factorial	Permutation enumeration

Common Patterns

Divide and Conquer: Split problem, solve recursively, combine

• Quick Sort, Merge Sort, Binary Search

Dynamic Programming: Optimal substructure + overlapping subproblems

• Knapsack, LCS, Edit Distance

Greedy: Local optimal choices lead to global optimum

• Huffman, Interval Scheduling, Dijkstra

Backtracking: Try all possibilities with pruning

• N-Queens, Subsets, Permutations

Choosing an Algorithm

Problem Type	Consider
Sorted array search	Binary Search
Shortest path	BFS (unweighted), Dijkstra (weighted)
String matching	KMP, Rabin-Karp
Optimization with constraints	DP, Greedy
All combinations	Backtracking
Streaming data	Reservoir Sampling, Count-Min, HLL