Divide & Conquer
Split the problem into independent subproblems, solve recursively, combine results.
Examples: Merge sort, quicksort, binary search, Strassen matrix multiply
Algorithms Hub
Understand how algorithms are defined, designed, and analyzed—then explore classic paradigms (greedy, DP, backtracking, divide and conquer) and the ideas behind P vs NP. Built for students, competitive programming, and interview prep.
Design
Complexity
Paradigms
What is an Algorithm?
An algorithm is a finite, step-by-step procedure to solve a problem or perform a computation. It takes input, follows unambiguous instructions, and produces output that terminates in a reasonable amount of time.
Algorithms are independent of programming language—you can express the same logic in C, Python, or Java. What matters is correctness (does it solve the problem?) and efficiency (how much time and memory does it use?).
Properties of a good algorithm
- Input — Zero or more well-defined inputs
- Output — At least one result related to the input
- Definiteness — Each step is precise and unambiguous
- Finiteness — Must terminate after a finite number of steps
- Effectiveness — Each step is simple enough to be carried out
Steps to Design an Algorithm
Whether you are writing pseudocode on paper or implementing in C, follow a repeatable design process:
- Understand the problem — Restate inputs, outputs, constraints, and edge cases (empty input, duplicates, overflow).
- Choose a representation — Decide arrays, linked lists, graphs, or other structures from the Data Structures Hub.
- Devise a plan — Pick a paradigm (brute force, greedy, DP, etc.) and sketch the high-level approach.
- Write pseudocode — Capture logic in plain language before coding syntax details.
- Analyze complexity — Estimate time and space with Big O notation.
- Implement & test — Code the solution and verify with small, boundary, and random cases.
- Optimize if needed — Improve time/space while preserving correctness.
Algorithm vs Pseudocode
An algorithm is the abstract idea; pseudocode is a human-readable draft of that idea. Source code is the machine-executable version.
| Aspect | Algorithm (concept) | Pseudocode | Program (code) |
|---|---|---|---|
| Purpose | Problem-solving strategy | Readable blueprint | Runnable implementation |
| Language | Language-neutral | Structured English + math | C, C++, Java, Python, etc. |
| Syntax | Informal description | Loose (IF, FOR, WHILE) | Strict compiler rules |
| Audience | Anyone learning the idea | Students, interview whiteboards | Computers / IDEs |
Example: Linear search
Algorithm idea: Scan the array left to right; return the index when the target is found, else return −1.
Algorithm LinearSearch(A, n, target)
for i ← 0 to n − 1
if A[i] = target
return i
return −1
The same logic becomes a C for loop with array indexing—pseudocode bridges concept and code.
Importance of Algorithm Design
Choosing the right algorithm often matters more than micro-optimizing code. Two programs that solve the same task can differ by orders of magnitude in runtime.
- Scalability — O(n²) may work for n = 100 but fail for n = 10⁶; O(n log n) scales to real data.
- Resource limits — Embedded systems, mobile apps, and cloud billing all care about memory and CPU.
- Interview & exams — Courses and coding screens test whether you can pick and justify an approach.
- Correctness under constraints — Greedy only works when proven safe; brute force may time out.
- Maintainability — Clear algorithmic structure makes code easier to debug and extend.
Rule of thumb: First make it correct, then measure complexity, then optimize the bottleneck—often by switching paradigm (e.g. from brute force to DP).
Time & Space Complexity
Time complexity counts how the number of basic operations grows with input size n. Space complexity counts extra memory beyond the input. We use Big O for worst-case upper bounds in interview and course contexts.
| Notation | Name | Example |
|---|---|---|
| O(1) | Constant | Array index access, hash lookup (average) |
| O(log n) | Logarithmic | Binary search |
| O(n) | Linear | Single pass through array |
| O(n log n) | Linearithmic | Merge sort, heap sort |
| O(n²) | Quadratic | Nested loops, naive bubble sort |
| O(2ⁿ) | Exponential | Naive recursive Fibonacci, subset generation |
| O(n!) | Factorial | Generating all permutations |
Space examples
- O(1) — In-place swap, two-pointer techniques with fixed variables
- O(n) — Auxiliary array, recursion stack depth n
- O(n²) — 2D DP table for many string/grid problems
Algorithm Analysis Tools
1. Asymptotic Notations
| Notation | Meaning | Example |
|---|---|---|
| Θ (Theta) | Tight bound | Θ(n²) means exactly quadratic growth rate |
| O (Big O) | Upper bound | O(n²) means at most quadratic |
| Ω (Omega) | Lower bound | Ω(n) means at least linear |
| o (Little o) | Strict upper bound | o(n²) means less than quadratic |
| ω (Little omega) | Strict lower bound | ω(n) means more than linear |
2. Recurrence Relations
Used to analyze recursive algorithms. Common recurrence solutions:
- T(n) = T(n/2) + O(1) → O(log n) — Binary search
- T(n) = 2T(n/2) + O(n) → O(n log n) — Merge sort
- T(n) = T(n−1) + O(n) → O(n²) — QuickSort worst case
- T(n) = T(n/2) + O(n) → O(n) — QuickSelect
- T(n) = 2T(n−1) + O(1) → O(2ⁿ) — Naive Fibonacci
3. Master Theorem
| Case | Condition | Solution |
|---|---|---|
| Case 1 | f(n) = O(nlogb(a) − ε) | T(n) = Θ(nlogb(a)) |
| Case 2 | f(n) = Θ(nlogb(a)) | T(n) = Θ(nlogb(a) · log n) |
| Case 3 | f(n) = Ω(nlogb(a) + ε) | T(n) = Θ(f(n)) |
Complexity Comparison Examples
Search in Data
| Algorithm | Time Complexity | When to Use |
|---|---|---|
| Linear search | O(n) | Unsorted data, small n |
| Binary search | O(log n) | Sorted data, large n |
| Hash table | O(1) average | Frequent lookups, key-value pairs |
Sorting Algorithms Comparison
| Algorithm | Best | Average | Worst | Space | Stable |
|---|---|---|---|---|---|
| QuickSort | O(n log n) | O(n log n) | O(n²) | O(log n) | No |
| Merge Sort | O(n log n) | O(n log n) | O(n log n) | O(n) | Yes |
| Heap Sort | O(n log n) | O(n log n) | O(n log n) | O(1) | No |
| Insertion Sort | O(n) | O(n²) | O(n²) | O(1) | Yes |
| Bubble Sort | O(n) | O(n²) | O(n²) | O(1) | Yes |
Algorithm Paradigms & Approaches
Different problem shapes call for different strategies. Below are the core paradigms covered across this hub and the Problem Solving Hub.
Dynamic Programming
Break into overlapping subproblems; cache optimal answers (memoization or tabulation).
Examples: Knapsack, LCS, edit distance, coin change
Start DP tutorialGreedy
Make the locally best choice at each step; requires proof that it yields a global optimum.
Examples: Activity selection, Huffman coding, Dijkstra (non-negative weights)
Start Greedy tutorialBacktracking
Build candidates incrementally; abandon paths that violate constraints (prune the search tree).
Examples: N-Queens, Sudoku, permutations/combinations, graph coloring
Start Backtracking tutorialBrute Force
Try all possibilities; simple to code but often exponential—baseline before optimizing.
Examples: All subsets, all pairs, password crack (small space)
Search & Sort
Foundational techniques: linear/binary search, sorting networks, two pointers, sliding window.
Examples: Binary search, merge sort, lower bound, two-sum sorted array
Algorithm Design Techniques (Detailed)
1. Incremental Approach
Build the solution step by step, maintaining a partial solution that grows until completion.
Examples: Insertion sort, selection sort, Dijkstra's shortest path
Key idea: Maintain an invariant that the partial solution is correct and extend it.
2. Decrease and Conquer
Reduce the problem to a smaller instance of the same problem, solve recursively, then extend the solution.
Examples: Binary search, insertion sort, topological sorting
Variations:
- Decrease by constant (insertion sort)
- Decrease by constant factor (binary search)
- Variable decrease
3. Transform and Conquer
Transform the problem into a different form that is easier to solve, solve it, then transform the solution back.
Examples: Heapsort (transform array to heap), Gaussian elimination, Horner's rule
Benefits: Can simplify complex problems by changing representation.
4. Branch and Bound
Systematic enumeration of candidate solutions using pruning to eliminate suboptimal branches.
Examples: Integer programming, traveling salesman (exact), knapsack (optimal)
Key difference from backtracking: Uses lower/upper bounds to prune, not just constraints.
5. Randomized Algorithms
Use random choices to guide the algorithm toward a solution, often providing probabilistic guarantees.
Examples: QuickSort (random pivot), Monte Carlo methods, randomized selection
Advantages: Often simpler and faster than deterministic counterparts.
6. Approximation Algorithms
Find near-optimal solutions for NP-hard problems with guaranteed performance bounds.
Examples: Vertex cover (2-approximation), traveling salesman (Christofides algorithm), set cover (logarithmic approximation)
When to use: When exact solutions are computationally infeasible.
P, NP & NP-Complete Problems
| Class | Meaning | Example |
|---|---|---|
| P | Solvable in polynomial time O(nk) by a deterministic machine | Sorting, shortest path (Dijkstra), linear search |
| NP | Solution can be verified in polynomial time (may be hard to find) | Boolean satisfiability (SAT), Hamiltonian cycle |
| NP-Complete | In NP and every NP problem reduces to it; no known poly-time algorithm | Traveling Salesman (decision), graph coloring, subset sum |
| NP-Hard | At least as hard as NP-complete; not necessarily in NP | Halting problem, optimization TSP |
The famous P vs NP question asks: can every problem whose solution is quickly verified also be quickly solved? It remains unsolved; practically, NP-complete problems are handled with approximation algorithms, heuristics, or exponential algorithms on small inputs.
For interviews: Focus on recognizing when a problem is likely NP-hard (exact cover, full TSP) and discuss trade-offs—exact DP for small n vs greedy/approximation for large n.
Algorithm Selection Guide
How to choose the right algorithm for a given problem:
Step 1: Understand Your Input
- Size: Small (n < 100) → any algorithm may work; large (n > 10⁶) → need O(n log n) or better
- Structure: Sorted/unsorted, graph/tree, streaming data
- Constraints: Memory limits, time limits
Step 2: Understand Your Requirements
- Accuracy: Exact solution vs approximation
- Speed: Online (real-time) vs offline
- Stability: Need stable sorting?
- In-place: Can we modify the input?
| Problem Type | Best Paradigm | Example |
|---|---|---|
| Optimization with overlapping states | Dynamic Programming | Knapsack, LCS |
| Optimal substructure, no overlap | Divide & Conquer | Merge sort |
| Locally optimal → globally optimal | Greedy | Activity selection |
| Constraint satisfaction | Backtracking | N-Queens |
| Search in sorted data | Binary Search | Searching |
| Graph traversal | BFS/DFS | Shortest path |
| Multiple constraints, large space | Approximation | TSP |
Step 4: Verify with Examples
- Test on small inputs mentally
- Check edge cases
- Compare with simpler alternatives
Common Algorithm Mistakes and How to Avoid Them
1. Off-by-One Errors
Problem: Incorrect loop boundaries or array indices.
Solution: Test with small cases (n=0, n=1, n=2) and use <= vs < carefully.
Problem: Incorrect loop boundaries or array indices.
Solution: Test with small cases (n=0, n=1, n=2) and use <= vs < carefully.
2. Infinite Loops
Problem: Loop condition never becomes false.
Solution: Ensure loop variables update correctly and termination condition is reachable.
Problem: Loop condition never becomes false.
Solution: Ensure loop variables update correctly and termination condition is reachable.
3. Stack Overflow in Recursion
Problem: Recursive depth exceeds system limits.
Solution: Use iterative approach, tail recursion, or increase stack size for deep recursion.
Problem: Recursive depth exceeds system limits.
Solution: Use iterative approach, tail recursion, or increase stack size for deep recursion.
4. Greedy Without Proof
Problem: Assuming greedy works when it doesn't.
Solution: Always prove greedy choice property or test against counterexamples.
Problem: Assuming greedy works when it doesn't.
Solution: Always prove greedy choice property or test against counterexamples.
5. DP State Definition Issues
Problem: Incorrect or incomplete state definition.
Solution: Clearly define what state represents and ensure all necessary information is included.
Problem: Incorrect or incomplete state definition.
Solution: Clearly define what state represents and ensure all necessary information is included.
6. Complexity Misestimation
Problem: Underestimating actual time/space requirements.
Solution: Count operations carefully; consider worst-case scenarios.
Problem: Underestimating actual time/space requirements.
Solution: Count operations carefully; consider worst-case scenarios.
7. Cache Invalidation (DP)
Problem: Not resetting memoization tables for multiple test cases.
Solution: Create fresh tables or use timestamp-based invalidation.
Problem: Not resetting memoization tables for multiple test cases.
Solution: Create fresh tables or use timestamp-based invalidation.
Advanced Topics Overview
1. Amortized Analysis
Analyzing the average time per operation over a sequence of operations.
Examples: Dynamic arrays (array list) — O(1) amortized per insertion; splay trees; disjoint set union (Union-Find)
Techniques: Aggregate method, accounting method, potential method
2. Parallel Algorithms
Algorithms designed to run on multiple processors simultaneously.
Key concepts: Work (total operations), span (longest dependency chain), speedup (sequential time / parallel time)
Examples: Parallel prefix sum, parallel merge sort, MapReduce patterns
3. Online Algorithms
Process input piece by piece without knowledge of future input.
Examples: Page replacement algorithms, online load balancing, cache algorithms
Performance metric: Competitive ratio (performance relative to offline optimal)
4. Streaming Algorithms
Process data that arrives in a stream, using limited memory.
Examples: Counting distinct elements (HyperLogLog), frequent elements (Boyer-Moore majority vote), reservoir sampling
Key constraints: Single pass, O(1) or O(log n) memory
5. Metaheuristics
High-level strategies for solving complex optimization problems.
Examples: Genetic algorithms, simulated annealing, ant colony optimization, particle swarm optimization
When to use: When exact solutions are too expensive and heuristics are acceptable.
Practice Problems Categorized
1. Basic Complexity
- Find max element in array → O(n)
- Two sum with hash map → O(n)
- Check if array is sorted → O(n)
- Palindrome checking → O(n)
- Compute factorial → O(n)
2. Divide & Conquer
- Merge sort implementation
- Quick sort with random pivot
- Binary search variants
- Maximum subarray (Kadane)
- Find peak element
3. Greedy
4. Dynamic Programming
- Fibonacci with memoization
- Climbing stairs
- 0/1 Knapsack
- Longest common subsequence
- Coin change
- Edit distance
- House robber
- Decode ways
5. Backtracking
6. Graph Problems
- BFS and DFS traversal
- Shortest path (Dijkstra, Bellman-Ford)
- Topological sort
- Minimum spanning tree
- Detect cycle in directed graph
Practice tutorials: Greedy, Backtracking, Dynamic Programming, and C programs in the Problem Solving Hub.
Interview Preparation Tips
1. Problem-Solving Framework
- Clarify — Ask questions to understand constraints
- Brainstorm — List possible approaches
- Evaluate — Compare complexity
- Design — Outline algorithm
- Implement — Write clean code
- Test — Run through examples
- Optimize — Suggest improvements
2. Common Interview Questions by Topic
Easy
- Two Sum
- Reverse linked list
- Valid parentheses
- Merge two sorted arrays
- Maximum subarray (Kadane)
Medium
- Longest substring without repeating
- Longest palindromic substring
- Coin change
- Combination sum
- Jump game
- Course schedule
Hard
- Median of two sorted arrays
- Wildcard matching
- Regular expression matching
- Word break II
- Minimum window substring
3. Time Management
- 5 minutes: Understand and clarify problem
- 5 minutes: Discuss approach and complexity
- 20 minutes: Code implementation
- 5 minutes: Test and debug
- 5 minutes: Discuss optimizations
4. Communication Tips
- Think out loud
- Explain trade-offs
- Discuss edge cases
- Ask for feedback
- Suggest improvements
Resources and References
Continue learning with structured tutorials and practice material on Nikhil Learn Hub:
- Dynamic Programming Tutorial — Full DP track with patterns and templates
- Greedy Algorithms Tutorial — Activity selection, knapsack, Huffman, coin change
- Backtracking Tutorial — N-Queens, Sudoku, permutations, word search
- Data Structures Hub — Arrays, lists, stacks, queues, trees, graphs
- Problem Solving Hub — C notes, MCQs, programs by topic
- C DP Notes — Dynamic programming in C
- C Greedy Notes — Greedy algorithms in C
- Cheatsheets Hub — Quick reference sheets
Recommended study flow: Algorithms Hub (concepts) → Data Structures → Greedy & Backtracking tutorials → DP deep-dive → interview practice with timed coding.
Suggested order: Master algorithm basics here → study data structures → Greedy & Backtracking → deep-dive Dynamic Programming → practice in the Problem Solving Hub.
Learning Paths
Dynamic Programming
Memoization, tabulation, knapsack, LIS, edit distance, and interview patterns.
Introduction to DP Memoization vs Tabulation Common DP Patterns
Greedy Algorithms
Locally optimal choices, activity selection, knapsack, Huffman coding, and coin change.
Introduction to Greedy Activity Selection Coin Change
Backtracking
Choose, explore, unchoose — N-Queens, Sudoku, permutations, maze, and word search.
Introduction to Backtracking N-Queens Word Search
Problem Solving (C)
Greedy, DP, backtracking, sorting, graphs—notes, MCQs, and programs.
Problem Solving Hub Greedy Notes Backtracking Notes
Data Structures
Arrays, lists, stacks, queues, trees, and graphs—the building blocks algorithms run on.
Data Structures Hub Stack Tutorial Graph Tutorial