October 17, 2026

Introduction to Algorithm Design Techniques

An algorithm is a step-by-step procedure used to solve a computational problem. Algorithm design techniques are general strategies that help programmers develop correct and efficient algorithms.

For example, suppose you need to sort 1,000,000 numbers. You could compare every number with every other number, but that approach would be inefficient. A better strategy, such as divide and conquer, can split the problem into smaller parts and combine their results.

Common algorithm design techniques include:

• Recursion

• Divide and conquer

• Greedy algorithms

• Backtracking

• Dynamic programming

Each technique is useful for a different category of problems. Choosing the appropriate technique can significantly improve an algorithm's performance.

1. Recursion in Algorithms

Recursion is a programming technique in which a function calls itself to solve a smaller version of the same problem.

A recursive function generally contains two important components:

1. Base case: Stops recursion when the problem becomes simple enough.

2. Recursive case: Calls the same function with a smaller or simpler input.

Without a valid base case, a recursive function may continue calling itself until the program runs out of stack space.

Example: Factorial Using Recursion

The factorial of a non-negative integer (n) is:

[
n! = n \times (n-1) \times \cdots \times 1
]

By definition:

[
0! = 1
]

The recursive definition is:

[
n! = n \times (n-1)!, \quad n > 0
]

C Program

#include 

long long factorial(int n) {
    if (n <= 1) {
        return 1;
    }

    return n * factorial(n - 1);
}

int main(void) {
    int n = 5;

    printf("Factorial of %d = %lld\n", n, factorial(n));

    return 0;
}

Output:

Factorial of 5 = 120

How It Works

The function calls itself with progressively smaller values:

factorial(5)
    5 * factorial(4)
        4 * factorial(3)
            3 * factorial(2)
                2 * factorial(1)
                    returns 1

The results then return through the call stack:

factorial(1) = 1
factorial(2) = 2
factorial(3) = 6
factorial(4) = 24
factorial(5) = 120

Time and Space Complexity

• Time complexity: (O(n))

• Auxiliary space complexity: (O(n)), due to recursive function calls.

This example is intended for non-negative inputs small enough that the result fits in long long. The program's base case returns 1 for negative inputs too, so a production implementation should validate the input explicitly.

Recursion vs Iteration

When to Use Recursion

Recursion is particularly useful for:

• Tree traversals

• Divide-and-conquer algorithms

• Backtracking problems

• Recursive mathematical definitions

• Graph traversal implementations

2. Divide and Conquer

Divide and conquer is an algorithm design technique that breaks a problem into smaller subproblems, solves them, and combines their results.

It usually follows three stages:

1. Divide: Split the original problem into smaller subproblems.

2. Conquer: Solve each subproblem, often recursively.

3. Combine: Merge the subproblem results into the final answer.

Merge Sort and many implementations of Binary Search use this general strategy.

Example: Merge Sort

Merge Sort divides an array into two halves, sorts each half recursively, and merges the sorted halves.

Suppose the input is:

38 27 43 3 9 82 10

The array is repeatedly split into smaller portions until each portion contains one element. The portions are then merged in sorted order.

C Program: Merge Sort

#include 

void merge(int arr[], int left, int mid, int right) {
    int temp[1000];
    int i = left;
    int j = mid + 1;
    int k = 0;

    while (i <= mid && j <= right) {
        if (arr[i] <= arr[j]) {
            temp[k++] = arr[i++];
        } else {
            temp[k++] = arr[j++];
        }
    }

    while (i <= mid) {
        temp[k++] = arr[i++];
    }

    while (j <= right) {
        temp[k++] = arr[j++];
    }

    for (i = left, k = 0; i <= right; i++, k++) {
        arr[i] = temp[k];
    }
}

void mergeSort(int arr[], int left, int right) {
    if (left >= right) {
        return;
    }

    int mid = left + (right - left) / 2;

    mergeSort(arr, left, mid);
    mergeSort(arr, mid + 1, right);
    merge(arr, left, mid, right);
}

int main(void) {
    int arr[] = {38, 27, 43, 3, 9, 82, 10};
    int n = sizeof(arr) / sizeof(arr[0]);

    mergeSort(arr, 0, n - 1);

    printf("Sorted array: ");

    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }

    printf("\n");

    return 0;
}

Output:

Sorted array: 3 9 10 27 38 43 82

The temporary array in this example has a capacity of 1,000 elements, so the program assumes the array length does not exceed 1,000. A reusable implementation should allocate temporary storage based on the input size and handle allocation failures.

Complexity of Merge Sort

Merge Sort divides the array into halves, producing approximately (\log_2 n) levels. At each level, merging processes (O(n)) elements.

Therefore:

• Best-case time: (O(n \log n))

• Average-case time: (O(n \log n))

• Worst-case time: (O(n \log n))

• Auxiliary space: (O(n))

Other Divide-and-Conquer Algorithms

• Binary Search: repeatedly reduces the search interval.

• Quick Sort: partitions an array around a pivot.

• Strassen's Matrix Multiplication: reduces the number of recursive matrix multiplications.

Important: Divide and conquer is not the same as dynamic programming. Divide and conquer typically solves independent subproblems, while dynamic programming is particularly useful when subproblems overlap and their results can be reused.

3. Greedy Algorithms

A greedy algorithm makes the best-looking local choice at each step according to a chosen rule. It does not generally reconsider earlier choices.

Greedy algorithms can be efficient, but a locally optimal choice does not always produce a globally optimal solution.

They are appropriate when the problem has properties that justify the greedy strategy, such as the greedy-choice property and, in many classic problems, optimal substructure.

Example: Coin Selection

Suppose we need to make a total of 63 using coin denominations:

25, 10, 5, 1

A greedy algorithm repeatedly selects the largest denomination that does not exceed the remaining amount.

C Program

#include 

int main(void) {
    int coins[] = {25, 10, 5, 1};
    int n = sizeof(coins) / sizeof(coins[0]);
    int amount = 63;

    printf("Coins selected: ");

    for (int i = 0; i < n; i++) {
        while (amount >= coins[i]) {
            printf("%d ", coins[i]);
            amount -= coins[i];
        }
    }

    printf("\n");

    return 0;
}

Output:

Coins selected: 25 25 10 1 1 1

The algorithm uses six coins to make 63.

For this denomination system, the greedy result is optimal. However, greedy coin selection is not optimal for every possible set of denominations.

For example, with denominations 1, 3, 4 and amount 6, greedy selection chooses 4 + 1 + 1, using three coins. The optimal solution is 3 + 3, using only two coins.

Applications of Greedy Algorithms

• Activity selection

• Fractional Knapsack

• Huffman coding

• Kruskal's Minimum Spanning Tree algorithm

• Prim's Minimum Spanning Tree algorithm

• Dijkstra's shortest-path algorithm when edge weights are non-negative

Complexity

The complexity depends on the greedy problem and implementation.

For the coin example, if the number of denominations is (k) and the amount is (A), the repeated-subtraction implementation can perform up to (O(A)) selections for fixed minimum coin value 1. It also has a loop over the denominations.

Greedy algorithms should be analyzed according to their actual implementation rather than assuming every greedy algorithm runs in (O(n)).

4. Backtracking

Backtracking is a problem-solving technique that builds a candidate solution step by step. When a partial solution violates a constraint or cannot lead to a valid result, the algorithm reverses that choice and tries another option.

Backtracking is useful for problems involving combinations, permutations, constraints, and search through possible states.

Common applications include:

• N-Queens

• Sudoku solvers

• Maze solving

• Generating permutations

• Subset-sum problems

Example: Generating All Binary Strings

Suppose we need to generate every binary string of length 3. Each position can contain either 0 or 1.

The possible strings are:

000
001
010
011
100
101
110
111

A backtracking algorithm chooses a value for the current position, recursively fills the next position, and returns to try the alternative value.

C Program

#include 

void generateBinary(char str[], int index, int n) {
    if (index == n) {
        str[index] = '\0';
        printf("%s\n", str);
        return;
    }

    str[index] = '0';
    generateBinary(str, index + 1, n);

    str[index] = '1';
    generateBinary(str, index + 1, n);
}

int main(void) {
    int n = 3;
    char str[4];

    generateBinary(str, 0, n);

    return 0;
}

Output:

000
001
010
011
100
101
110
111

How It Works

• The function fills one position at a time.

• It tries 0 and recursively generates all continuations.

• It then tries 1 and generates those continuations.

• When all positions are filled, it prints the string.

For a general length (n), there are (2^n) binary strings, so the time complexity is (O(2^n)) for generating and printing all strings, ignoring constant factors associated with output.

The auxiliary recursion depth is (O(n)).

Backtracking vs Brute Force

Backtracking explores candidate solutions systematically and can prune invalid partial candidates before completing them. Brute force often checks every candidate, even when some could have been rejected earlier.

The efficiency of backtracking depends on how effectively it prunes the search space. In the binary-string example, there are no constraints to prune, so all (2^n) strings must be generated.

5. Dynamic Programming Basics

Dynamic Programming (DP) is a technique for solving problems by breaking them into overlapping subproblems and storing the results so that the same work does not need to be repeated.

DP is often useful when a problem has:

1. Overlapping subproblems: The same smaller problems appear multiple times.

2. Optimal substructure: An optimal solution can be constructed from appropriate solutions to smaller subproblems.

There are two common approaches:

• Memoization: Top-down recursion with cached results.

• Tabulation: Bottom-up calculation using a table or array.

Example: Fibonacci Numbers

The Fibonacci sequence is defined as:

[
F(0)=0,\quad F(1)=1
]

[
F(n)=F(n-1)+F(n-2),\quad n\geq2
]

A direct recursive implementation repeats many calculations. For example, calculating fib(5) calculates fib(3) more than once.

Dynamic programming avoids this repeated work.

C Program: Fibonacci Using Tabulation

#include 

int main(void) {
    int n = 10;
    long long fib[100];

    if (n < 0 || n >= 100) {
        printf("Invalid input\n");
        return 1;
    }

    fib[0] = 0;

    if (n >= 1) {
        fib[1] = 1;
    }

    for (int i = 2; i <= n; i++) {
        fib[i] = fib[i - 1] + fib[i - 2];
    }

    printf("Fibonacci series: ");

    for (int i = 0; i <= n; i++) {
        printf("%lld ", fib[i]);
    }

    printf("\n");

    return 0;
}

Output:

Fibonacci series: 0 1 1 2 3 5 8 13 21 34 55

Complexity

For this tabulation approach:

• Time complexity: (O(n))

• Auxiliary space complexity: (O(n))

If only the most recent two Fibonacci values are needed, the sequence can be computed using two variables, reducing auxiliary space to (O(1)).

Memoization Example

Memoization stores the results of recursive calls so that they are calculated only once.

#include 

long long memo[100];

long long fib(int n) {
    if (n <= 1) {
        return n;
    }

    if (memo[n] != -1) {
        return memo[n];
    }

    memo[n] = fib(n - 1) + fib(n - 2);

    return memo[n];
}

int main(void) {
    int n = 10;

    for (int i = 0; i < 100; i++) {
        memo[i] = -1;
    }

    printf("Fibonacci(%d) = %lld\n", n, fib(n));

    return 0;
}

Output:

Fibonacci(10) = 55

The program assumes n is between 0 and 99. A production version should validate the input and account for the numeric range of long long.

Applications of Dynamic Programming

• Fibonacci calculations

• 0/1 Knapsack

• Longest Common Subsequence

• Longest Increasing Subsequence

• Edit Distance

• Matrix Chain Multiplication

• Shortest paths in appropriate graph algorithms

Greedy vs Dynamic Programming

6. Algorithm Complexity Analysis

Algorithm complexity analysis estimates how an algorithm's resource usage grows as the input size increases.

The two major measures are:

• Time complexity: How the number of operations grows with input size.

• Space complexity: How memory usage grows with input size.

Complexity is usually described using asymptotic notation, especially Big O notation for an upper bound on growth.

Common Time Complexities

These examples describe typical algorithmic growth, not every implementation of a problem.

Example: Linear Time

#include 

int main(void) {
    int arr[] = {10, 20, 30, 40, 50};
    int n = sizeof(arr) / sizeof(arr[0]);

    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }

    printf("\n");

    return 0;
}

Output:

10 20 30 40 50

The loop processes each of the (n) elements once. Therefore, time complexity is (O(n)).

Example: Quadratic Time

#include 

int main(void) {
    int n = 4;

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            printf("(%d,%d) ", i, j);
        }
        printf("\n");
    }

    return 0;
}

Output:

(0,0) (0,1) (0,2) (0,3)
(1,0) (1,1) (1,2) (1,3)
(2,0) (2,1) (2,2) (2,3)
(3,0) (3,1) (3,2) (3,3)

The outer loop runs (n) times, and the inner loop runs (n) times for each outer iteration. The total number of iterations is (n^2), so time complexity is (O(n^2)).

Complexity of Techniques Covered in This Module

Complexity depends on the exact algorithm and implementation. For recursive algorithms, auxiliary space should include the maximum active recursion depth. For algorithms that generate output, writing the output also contributes to the running time.

Best Practices for Algorithm Design

1. Understand the problem and its constraints before selecting a technique.

2. Identify the base cases for recursive algorithms.

3. Use divide and conquer when a problem can be split into manageable subproblems.

4. Verify the correctness of a greedy strategy before assuming it produces an optimal solution.

5. Use backtracking to explore constrained choices and prune invalid candidates.

6. Use dynamic programming when overlapping subproblems can be solved efficiently by reusing results.

7. Analyze both time and auxiliary space complexity.

8. Test edge cases, including empty inputs, small values, and maximum supported sizes.

9. Check integer limits and memory allocation in C programs.

10. Prefer the simplest algorithm that satisfies the performance and correctness requirements.

Conclusion

Algorithm design techniques help programmers build solutions that are correct, maintainable, and efficient.

In this module, we covered all six curriculum topics:

1. Recursion in Algorithms

2. Divide and Conquer

3. Greedy Algorithms

4. Backtracking

5. Dynamic Programming Basics

6. Algorithm Complexity Analysis

The key lesson is that no single technique is best for every problem. Recursion is useful for self-similar problems, divide and conquer splits problems into smaller parts, greedy algorithms make justified local choices, backtracking explores candidate solutions, and dynamic programming reuses subproblem results.

Understanding these techniques prepares you to design algorithms for real-world applications and tackle more advanced DSA problems.