Essential Algorithms: Complexity, Divide and Conquer, and KMP

Posted on Apr 23, 2026 in Computer Engineering

1. Space Complexity

The space complexity of an algorithm is the amount of memory it needs to run to completion. The space required by a program includes the following components:

  • Instruction space: The space needed to store the compiled version of the program instructions.
  • Data space: The space needed to store all constant and variable values. This includes:
    • Space needed by constants and simple variables.
    • Space needed by dynamically allocated objects such as arrays and class instances.
  • Environment stack space: Used to save information needed to resume execution of partially completed functions.
  • Instruction space factors: Depends on the compiler used and the compiler options in effect.

Example: Algorithm abc(a,b,c) { return a + b++ * c + (a+b-c)/(a+b) + 4; }

2. Divide and Conquer Method

In the divide and conquer approach, the problem is divided into smaller sub-problems, which are solved independently. When sub-problems are divided until no further division is possible, the solutions are merged to obtain the final result.

Steps:

  1. Divide/Break: Breaking the problem into smaller sub-problems recursively.
  2. Conquer/Solve: Solving the smaller sub-problems.
  3. Merge/Combine: Recursively combining the solutions to form the original solution.

3. Longest Common Subsequence (LCS)

The LCS of two sequences is the longest sequence that appears in both in the same order, but not necessarily contiguously.

Example: X = “ABCBDAB”, Y = “BDCABA” → LCS = “BCBA”

Algorithm Steps:

  • Create a 2D table of size (m+1) × (n+1).
  • Initialize the first row and column as 0.
  • Fill the table using the recurrence: If characters match, take diagonal + 1; else, take the max of top or left.
  • Final answer is found at L[m][n].

4. Asymptotic Notations

  • Big O (O): f(n) is bounded above by c*g(n) for all n ≥ n0.
  • Big Omega (Ω): f(n) is bounded below by c*g(n) for all n ≥ n0.
  • Big Theta (Θ): f(n) is bounded both above and below by constant multiples of g(n).

5. Knuth-Morris-Pratt (KMP) Algorithm

The KMP algorithm provides a linear time complexity O(n) for string matching by avoiding redundant comparisons. It ensures that backtracking on the text never occurs.

Key Concepts:

  • Prefix Function (π): Encapsulates knowledge about how the pattern matches against shifts of itself to avoid useless shifts.
  • LPS Array (Longest Prefix Suffix): Stores the length of the longest proper prefix that is also a suffix.

Advantages:

  • No rechecking of characters.
  • Faster than naive approaches.
  • Efficient for large texts.

6. Time Complexity

Time complexity is the amount of computer time needed to run an algorithm to completion. Asymptotic time complexity determines the scalability of an algorithm.

Example: For Algorithm sum(a,n), each invocation executes a total of 2n+3 steps.