Common Algorithms

 

1. Sorting Algorithms

Algorithm	Time Complexity (Best / Avg / Worst)	Space Complexity	Stable?	When to Use
Bubble Sort	O(n) / O(n²) / O(n²)	O(1)	✅ Yes	Simple, but inefficient for large datasets
Selection Sort	O(n²) / O(n²) / O(n²)	O(1)	❌ No	When swapping is costly, but still inefficient
Insertion Sort	O(n) / O(n²) / O(n²)	O(1)	✅ Yes	Works well for nearly sorted arrays
Merge Sort	O(n log n) / O(n log n) / O(n log n)	O(n)	✅ Yes	Large datasets, stable sorting
Quick Sort	O(n log n) / O(n log n) / O(n²)	O(log n)	❌ No	Fastest for general use, but unstable
Heap Sort	O(n log n) / O(n log n) / O(n log n)	O(1)	❌ No	Best when you need a min/max priority queue
Counting Sort	O(n + k) / O(n + k) / O(n + k)	O(k)	✅ Yes	When range of numbers is small (k ≈ n)

Quick Tip:

• Use Merge Sort if stability is required.
• Use Quick Sort for average-case speed and efficiency.
• Use Counting Sort if numbers have a small range.

---

2. Searching Algorithms

Algorithm	Time Complexity	When to Use
Linear Search	O(n)	Unsorted data or small datasets
Binary Search	O(log n)	Sorted arrays only
Jump Search	O(√n)	Sorted arrays where Binary Search is expensive
Interpolation Search	O(log log n)	Sorted data with uniformly distributed values

Quick Tip:

• Binary Search is the go-to for sorted data!
• Interpolation Search is useful when the dataset is uniformly distributed.

---

3. Graph Algorithms

Algorithm	Use Case	Time Complexity
Depth-First Search (DFS)	Tree/graph traversal	O(V + E)
Breadth-First Search (BFS)	Shortest path in unweighted graphs	O(V + E)
Dijkstra’s Algorithm	Shortest path in weighted graphs	O((V + E) log V)
Floyd-Warshall Algorithm	All-pairs shortest paths	O(V³)
Bellman-Ford Algorithm	Shortest path with negative weights	O(VE)
Topological Sorting (Kahn’s Algorithm)	DAG ordering	O(V + E)

Quick Tip:

• Use DFS for deep exploration (e.g., cycle detection).
• Use BFS for shortest paths in unweighted graphs.
• Use Dijkstra’s Algorithm for shortest paths with positive weights.
• Use Floyd-Warshall for all-pairs shortest paths when the graph is small.

---

4. Dynamic Programming (DP) Algorithms

Problem Type	Algorithm	Time Complexity
Fibonacci Sequence	Memoization / Tabulation	O(n)
Knapsack Problem (0/1)	DP	O(nW)
Longest Common Subsequence (LCS)	DP	O(mn)
Longest Increasing Subsequence (LIS)	DP	O(n²) (O(n log n) with binary search)
Edit Distance (Levenshtein Distance)	DP	O(mn)

Quick Tip:

• Memoization (Top-down) → Recursive + caching results.
• Tabulation (Bottom-up) → Filling up a DP table iteratively.

---

5. Greedy Algorithms

Problem Type	Algorithm	Time Complexity
Activity Selection	Greedy	O(n log n)
Huffman Coding	Greedy + Heap	O(n log n)
Kruskal’s Algorithm (MST)	Greedy	O(E log E)
Prim’s Algorithm (MST)	Greedy + PQ	O(E log V)

📌 Quick Tip:

• Greedy algorithms make local optimal choices to get a global solution.
• Use them when sorting + selection leads to the best solution.

---

6. Number Theory Algorithms

Algorithm	Use Case	Time Complexity
GCD (Euclidean Algorithm)	Find GCD of two numbers	O(log n)
Sieve of Eratosthenes	Find all prime numbers ≤ n	O(n log log n)
Modular Exponentiation	Efficient exponentiation	O(log n)

Quick Tip:

• Sieve of Eratosthenes is the best way to find primes ≤ n.
• Use modular exponentiation for large powers under a modulus.

---

Summary of Key Takeaways

Problem Type	Best Algorithm
Searching	Binary Search (for sorted data)
Sorting	Merge Sort (Stable), Quick Sort (Fastest avg case)
Graph Traversal	DFS (Deep search), BFS (Shortest unweighted path)
Shortest Path	Dijkstra (Weighted graphs, no negative edges)
Optimization	Dynamic Programming (Subproblems with dependencies)
Prime Numbers	Sieve of Eratosthenes (O(n log log n))
GCD Calculation	Euclidean Algorithm (O(log n))

---

 

Use Case	Best Choice
General-purpose storage (mixed types), dynamic resizing	list	Mutable, ordered, allows duplicates
Immutable, fixed data (coordinates, fixed records)	tuple	Immutable, ordered, allows duplicated
Unique values, fast membership test	set	Mutable, unordered, no duplicates
Key-value pairs, fast lookups (O(1))	dict	Mutable, ordered
Memory-efficient number storage for same-type	array.array	Mutable, ordered, fixed datatype
High-performance numerical computing (ML, large datasets)	numpy.ndarray	Mutable, ordered, fixed datatype, vectorized operations