O(n²): Quadratic Time
You'll learn why some algorithms slow down dramatically as input grows, and recognize the nested loop pattern that causes this.
What Makes an Algorithm Quadratic?
An algorithm runs in quadratic time when its number of operations grows proportional to the square of the input size. If you double the input size, the algorithm takes roughly four times as long to run. Triple the input? Nine times longer.
The telltale sign: nested loops where both iterate through the input.
The Nested Loop Pattern
Consider checking for duplicate elements by comparing every element with every other element:
for i from 0 to n-1:
for j from 0 to n-1:
compare array[i] with array[j]
The outer loop runs n times. For each of those iterations, the inner loop also runs n times. Total operations: n × n = n².
Real Example: Bubble Sort
Bubble sort repeatedly steps through an array, comparing adjacent elements and swapping them if they're in the wrong order. This requires:
- An outer loop to make multiple passes through the array
- An inner loop to compare and swap adjacent elements
Even though bubble sort does less work on each pass, you still have one loop nested inside another, both dependent on input size — classic O(n²) behavior.
Why Quadratic Is Costly
For an array of 10 elements: ~100 operations. For 100 elements: ~10,000 operations. For 1,000 elements: ~1,000,000 operations!
This rapid growth makes quadratic algorithms impractical for large datasets.
Key Takeaway: O(n²) complexity comes from nested loops iterating over input, causing operations to grow with the square of input size — acceptable for small data, but quickly becomes prohibitively slow as data grows.