Named algorithms in computer science

There are dozens of named algorithms in computer science, each addressing specific problems efficiently. Below are some of the most famous ones, categorized by their application:

📌 Famous Named Algorithms in Computer Science

1️⃣ Array & Sequence Processing

Kadane’s Algorithm → Finds the maximum subarray sum in O(n).

Dutch National Flag Algorithm → Sorts an array of three distinct values in O(n) (Used in quicksort 3-way partitioning).

Floyd’s Tortoise and Hare Algorithm → Detects cycles in linked lists or sequences in O(n) with O(1) space.

2️⃣ Sorting Algorithms

Merge Sort → Divide & Conquer-based sorting algorithm in O(n log n).

QuickSort → Efficient sorting using partitioning (O(n log n) on average).

Heap Sort → Uses a heap to sort in O(n log n).

Counting Sort → Fast sorting in O(n + k) for small integer ranges.

Radix Sort → Non-comparative sorting in O(nk).

3️⃣ Searching Algorithms

Binary Search → Efficiently searches in O(log n).

Interpolation Search → Improved binary search for uniformly distributed numbers in O(log log n).

Jump Search → Jumps fixed steps for faster search in sorted arrays in O(√n).

Exponential Search → Good for unbounded search spaces, works in O(log n).

4️⃣ Graph Algorithms

Dijkstra’s Algorithm → Finds shortest paths from a source in O(V + E log V).

Bellman-Ford Algorithm → Finds shortest paths even with negative weights in O(VE).

Floyd-Warshall Algorithm → Computes all-pairs shortest paths in O(V³).

Prim’s Algorithm → Finds the Minimum Spanning Tree (MST) using a greedy approach in O(E log V).

Kruskal’s Algorithm → Finds MST using union-find in O(E log E).

Tarjan’s Algorithm → Finds strongly connected components in O(V + E).

Kosaraju’s Algorithm → Another approach to find strongly connected components in O(V + E).

A Search Algorithm* → Finds shortest paths using heuristics, commonly used in AI.

5️⃣ Dynamic Programming (DP) Algorithms

Fibonacci DP → Computes Fibonacci numbers efficiently in O(n).

Knapsack Algorithm → Solves the 0/1 Knapsack problem in O(nW).

Longest Common Subsequence (LCS) → Finds longest shared subsequence in O(mn).

Longest Palindromic Subsequence → Solves palindrome-based problems in O(n²).

Edit Distance (Levenshtein Algorithm) → Measures similarity between two strings in O(mn).

6️⃣ Greedy Algorithms

Huffman Coding Algorithm → Compression technique in O(n log n).

Activity Selection Algorithm → Selects max non-overlapping activities in O(n log n).

Egyptian Fraction Algorithm → Represents fractions using unique unit fractions.

7️⃣ Tree & Heap Algorithms

Binary Tree Traversals (Inorder, Preorder, Postorder, Level Order) → Standard O(n) traversals.

Segment Tree Algorithm → Efficient range queries in O(log n).

Fenwick Tree (Binary Indexed Tree - BIT) → Fast prefix sum queries in O(log n).

Union-Find (Disjoint Set Union - DSU) → Efficiently manages dynamic connectivity in O(α(n)).

8️⃣ String Processing Algorithms

KMP Algorithm (Knuth-Morris-Pratt) → Efficient pattern searching in O(n + m).

Rabin-Karp Algorithm → Uses rolling hash for pattern matching in O(n + m).

Z-Algorithm → Finds pattern occurrences efficiently in O(n + m).

Manacher’s Algorithm → Finds the longest palindromic substring in O(n).

Aho-Corasick Algorithm → Multi-pattern string matching in O(n + m + k).

9️⃣ Bit Manipulation Algorithms

Brian Kernighan’s Algorithm → Counts set bits in O(log n).

XOR Trick → Finds missing or duplicate numbers in arrays efficiently.

Gray Code Algorithm → Generates sequences with minimal bit changes.

🔟 Miscellaneous Algorithms

Reservoir Sampling Algorithm → Randomly selects elements from a stream in O(1) per selection.

Monte Carlo Algorithm → Probabilistic algorithms used in simulations.

Miller-Rabin Algorithm → Primality test in O(log n).

Booth’s Algorithm → Efficiently finds the lexicographically smallest rotation of a string.

📝 Summary

These named algorithms are the building blocks of problem-solving in competitive programming, interviews, and real-world applications.