Course contentsShow
← Python
Lesson 117 of 1,0602. Control Flow and LogicFree lesson

Calculating Algorithmic Complexity of Nested Loops

Determine the time complexity of nested structures using Big O notation to predict how execution time scales with input size.

Calculating Algorithmic Complexity of Nested Loops

In this lesson, you will learn how to determine the efficiency of your code by calculating how execution time scales as your input size grows.

When you write a single loop, the number of operations usually grows linearly with the size of your input, denoted as O(n). However, when you place one loop inside another, the relationship changes significantly.

Understanding Nested Growth

Imagine you have a list of items with length n. If you create a nested loop to compare every item against every other item, you are performing a "nested" action. For every single iteration of the outer loop, the inner loop runs completely from start to finish.

# A nested loop structure
for i in range(n):        # Runs 'n' times
    for j in range(n):    # Runs 'n' times for EACH 'i'
        print(i, j)

In the code above, the inner loop executes n times for every one of the n outer iterations. Mathematically, this is n * n, which is n^2. In Big O notation, we call this Quadratic Time or O(n^2).

Why It Matters

As your input size n increases, O(n^2) grows much faster than O(n). If your list has 10 items, O(n) performs 10 operations, while O(n^2) performs 100. If you increase that list to 1,000 items, O(n) stays manageable at 1,000 operations, but the nested loop jumps to 1,000,000 operations!

When you analyze your nested loops, simply ask: "How many times does the inner body execute relative to the input?" If the inner loop depends on the outer loop’s size, you are looking at multiplicative growth. Recognizing this pattern is the first step in identifying parts of your program that might become slow as your data sets grow larger.

Key Takeaway: Nested loops typically result in O(n^2) time complexity, meaning that doubling your input size can quadruple the time it takes for your code to finish.