Grokking Algorithm Complexity and Big-O
Ask Author
Back to course home

0% completed

Vote For New Content
Quadratic Space: O(n²)
On this page

Key Characteristics

Code Example: Longest Common Subsequence (LCS)

Examples of O(n^2) Space Operations

Quadratic Space Complexity O(n^2) describes algorithms where the memory usage grows proportionally to the square of the input size. This type of complexity is common in dynamic programming (DP) problems that require a 2D table to store intermediate results, especially when solving problems involving grids or pairs.

Key Characteristics

In an algorithm with O(n^2) space complexity:

  • Memory usage grows with the square of the input size.
  • This is typical in algorithms that use a 2D array or matrix to store information for each pair of elements or each cell in a grid.

Code Example: Longest Common Subsequence (LCS)

The Longest Common Subsequence (LCS) problem is a classic DP problem where we use a 2D table to store the length of the longest common subsequence between prefixes of two strings.

Python3
Python3
. . . .
  • Explanation:
    • The dp table has dimensions (m+1) x (n+1), where m and n are the lengths of the two strings X and Y.
    • Each cell dp[i][j] stores the length of the LCS of the prefixes X[0...i-1] and Y[0...j-1].
    • This results in a quadratic space complexity of O(m*n).
Image

Examples of O(n^2) Space Operations

  • Dynamic Programming on Grids: Problems that involve 2D grids, like pathfinding in a matrix.
  • Pair-Based DP Problems: Problems like LCS or edit distance, where we track values for each combination of positions in two strings.
  • Graph Algorithms with Adjacency Matrices: Representing a graph with an adjacency matrix uses O(n^2) space for a graph with n nodes.

.....

.....

.....

Like the course? Get enrolled and start learning!

On this page

Key Characteristics

Code Example: Longest Common Subsequence (LCS)

Examples of O(n^2) Space Operations