8. Analyzing Quadratic Time: O(N²)

An algorithm runs in Quadratic Time, O(N²), if the execution time grows proportionally to the square of the input size (N).

If the input doubles (N becomes 2N), the execution time quadruples (N² becomes 4N²).

Example: Nested Loops

The classic example of O(N²) is having two nested loops, where the inner loop fully iterates for every iteration of the outer loop.

python def print_all_pairs(data): N = len(data) # Outer loop runs N times (O(N)) for i in range(N): # Inner loop runs N times for each outer iteration (O(N)) for j in range(N): print(data[i], data[j]) # Total operations = N * N = N²

Algorithms with O(N²) complexity (like Bubble Sort, which we'll cover later) are generally considered slow and inefficient for large datasets.