Course contentsShow
← Computer Science
Lesson 288 of 2,8727. Introduction to Complexity AnalysisFree lesson

O(n³) and Higher Polynomial Time

Recognizing cubic and higher-degree polynomial complexities from multiple nested loops and matrix operations.

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: n rows of result
  • Middle loop: n columns of result
  • Inner loop: n multiplications 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.