Algorithm design techniques are standard problem-solving strategies used to build efficient algorithms. Instead of inventing a new method for every problem, we study a small set of powerful techniques and learn when to apply each one.
These techniques are important because many problems in sorting, searching, optimization, graphs, and recursion follow common patterns. Once you recognize the pattern, choosing the right technique becomes much easier.
Different problems require different ways of thinking. A direct brute-force solution may be correct, but it is often too slow for large input sizes. Design techniques help us create solutions that are:
| Technique | Main Idea | Best Used For | Examples |
|---|---|---|---|
| Divide and Conquer | Split, solve smaller parts, then combine | Problems that can be broken into independent subproblems | Merge Sort, Quick Sort, Binary Search |
| Greedy Method | Take the best immediate choice at each step | Problems where local choices lead to a global optimum | Activity Selection, Kruskal, Huffman Coding |
| Dynamic Programming | Store results of repeated subproblems | Optimization problems with overlapping subproblems | Knapsack, Fibonacci, LCS |
| Backtracking | Try choices, undo wrong ones, continue searching | Constraint satisfaction and exhaustive search | N-Queens, Sudoku, Maze solving |
| Branch and Bound | Search with bounds to discard bad branches early | Hard optimization problems | TSP, 0/1 Knapsack |
| Randomized | Use randomness to improve expected performance | When worst-case patterns should be avoided | Randomized Quick Sort, Monte Carlo methods |
Before selecting a technique, ask the following questions:
The answers to these questions often directly point to divide and conquer, dynamic programming, greedy, backtracking, or branch and bound.
Divide and Conquer solves a problem by splitting it into smaller independent subproblems, solving them recursively, and combining their results.
When it works well: When subproblems are independent and the combine step is efficient.
Common examples: Merge Sort, Quick Sort, Binary Search, Strassen Matrix Multiplication.
public class BinarySearch {
static int search(int[] arr, int low, int high, int target) {
if (low > high) {
return -1;
}
int mid = low + (high - low) / 2;
if (arr[mid] == target) {
return mid;
}
if (target < arr[mid]) {
return search(arr, low, mid - 1, target);
}
return search(arr, mid + 1, high, target);
}
public static void main(String[] args) {
int[] arr = {3, 8, 14, 19, 27, 31, 42, 56};
System.out.println(search(arr, 0, arr.length - 1, 27));
System.out.println(search(arr, 0, arr.length - 1, 10));
}
}
/*
Analysis
- Each step cuts the search space into half
- Time Complexity: O(log n)
- Space Complexity: O(log n) due to recursion
*/Greedy algorithms build a solution step by step by always choosing the option that looks best at the current moment. The choice is not reconsidered later.
When it works well: Scheduling, minimum spanning trees, shortest path with non-negative weights, data compression.
Main limitation: Greedy is fast, but it does not always guarantee the best answer.
public class ActivitySelection {
static void selectActivities(int[] start, int[] finish) {
int n = start.length;
int last = 0;
System.out.println("Selected activities:");
System.out.println("Activity 0");
for (int i = 1; i < n; i++) {
if (start[i] >= finish[last]) {
System.out.println("Activity " + i);
last = i;
}
}
}
public static void main(String[] args) {
int[] start = {1, 3, 0, 5, 8, 5};
int[] finish = {2, 4, 6, 7, 9, 9};
selectActivities(start, finish);
}
}
/*
Greedy idea:
- Always choose the activity that finishes earliest
- This leaves maximum room for future activities
*/Dynamic Programming (DP) is used when a problem has repeated subproblems. Instead of solving the same subproblem again and again, we store the result and reuse it.
When it works well: Knapsack, Fibonacci, LCS, matrix chain multiplication, shortest path in weighted graphs.
public class FibonacciDP {
static long fibonacci(int n) {
if (n <= 1) {
return n;
}
long[] dp = new long[n + 1];
dp[0] = 0;
dp[1] = 1;
for (int i = 2; i <= n; i++) {
dp[i] = dp[i - 1] + dp[i - 2];
}
return dp[n];
}
public static void main(String[] args) {
System.out.println(fibonacci(10));
System.out.println(fibonacci(50));
}
}
/*
Analysis
- Naive recursion: O(2^n)
- DP version: O(n)
- Extra space: O(n)
*/Backtracking tries to build a solution step by step. If a partial solution becomes invalid, the algorithm undoes the last choice and tries another path.
When it works well: Constraint satisfaction problems, permutations, combinations, puzzles, path finding.
Main limitation: The worst-case time is often exponential, but pruning can still make it practical.
public class Permutations {
static void swap(char[] arr, int i, int j) {
char temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
static void generate(char[] arr, int index) {
if (index == arr.length) {
System.out.println(new String(arr));
return;
}
for (int i = index; i < arr.length; i++) {
swap(arr, index, i);
generate(arr, index + 1);
swap(arr, index, i);
}
}
public static void main(String[] args) {
generate("ABC".toCharArray(), 0);
}
}Branch and Bound is an advanced search technique used mainly for optimization problems. It is similar to backtracking, but instead of exploring every possibility blindly, it calculates a bound for each partial solution.
When it works well: Travelling Salesman Problem, assignment problem, integer programming, 0/1 Knapsack.
Compared to plain backtracking, branch and bound usually prunes more aggressively because it uses a numerical estimate of how good a branch can still become.
Randomized algorithms use random choices as part of their logic. The goal is usually to improve average performance, simplify the method, or avoid specially crafted worst-case inputs.
Examples: Randomized Quick Sort, randomized selection, Monte Carlo algorithms, Las Vegas algorithms.
| Technique | Strength | Weakness | Typical Complexity Pattern |
|---|---|---|---|
| Divide and Conquer | Very efficient for recursive splitting problems | Not useful if subproblems heavily overlap | Often O(n log n) or O(log n) |
| Greedy | Simple and fast | May fail to find the optimal answer | Often polynomial |
| Dynamic Programming | Converts exponential recursion into polynomial time | May require large memory tables | Often O(n^2), O(nW), or similar |
| Backtracking | Can find exact solutions for constraint problems | Worst case often exponential | Often O(b^d) |
| Branch and Bound | Better pruning for optimization problems | Still expensive for very large search spaces | Problem-dependent |
| Randomized | Strong expected performance | Result may depend on probability | Expected complexity usually analyzed |
| If the Problem Looks Like... | Technique to Consider | Reason |
|---|---|---|
| Repeated smaller independent parts | Divide and Conquer | The problem naturally splits and combines |
| Repeated subproblems in recursion | Dynamic Programming | Stored results prevent recomputation |
| Best immediate choice appears safe | Greedy | Local optimum may lead to global optimum |
| Need to test many combinations with constraints | Backtracking | Invalid partial solutions can be rejected early |
| Optimization with expensive search space | Branch and Bound | Bounds help skip hopeless branches |
| Worst-case inputs should be avoided probabilistically | Randomized | Random choices improve expected behavior |
After understanding algorithm design techniques, the next useful topic is asymptotic notation. It helps you measure and compare how efficient each technique really is as the input size grows.
Explore 500+ free tutorials across 20+ languages and frameworks.