O(n³) and Higher Polynomial Time
You'll learn: How to recognize cubic and higher-degree polynomial time complexities from code patterns like triple-nested loops and certain matrix operations.
The Core Idea
When you nest three loops where each depends on the input size n, you get O(n³) — cubic time complexity. This means if you double your input size, the runtime increases by roughly 8 times (2³ = 8). Similarly, four nested loops give you O(n⁴), and so on. These are called polynomial complexities of degree 3 or higher.
Recognizing O(n³) in Code
The classic pattern is three nested loops all running proportional to n:
for i from 0 to n:
for j from 0 to n:
for k from 0 to n:
// constant-time operation
This executes the innermost operation n × n × n = n³ times.
Real-World Example: Matrix Multiplication
Standard matrix multiplication of two n×n matrices is O(n³):
- Outer loop:
nrows of result - Middle loop:
ncolumns of result - Inner loop:
nmultiplications per cell
Each cell requires n operations, and there are n² cells total: n² × n = n³.
When Complexity Gets Even Higher
Four nested loops? That's O(n⁴). Five? O(n⁵). These quickly become impractical for large inputs — even moderate input sizes can take hours or days.
Growth Impact
With n=10: O(n³) ≈ 1,000 operations
With n=100: O(n³) ≈ 1,000,000 operations
With n=1,000: O(n³) ≈ 1,000,000,000 operations
Key Takeaway: O(n³) and higher polynomial complexities arise from multiple nested loops (three or more) and operations like matrix multiplication — they scale poorly and require careful optimization or algorithmic improvements for large datasets.