Quadratic Space: O(n²)

Grokking Algorithm Complexity and Big-O

Ask Author

Back to course home

0% completed

Vote For New Content

Quadratic Space: O(n²)

Table of Contents

Contents are not accessible

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

. . . .

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)$ .

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!

Table of Contents

Contents are not accessible

Key Characteristics

Code Example: Longest Common Subsequence (LCS)

Examples of O(n^2) Space Operations

Examples of $O(n^2)$ Space Operations