Big-O of Iterative Code: Loops and Nested Loops

The Building Blocks: From Simple Statements to Loops

Let's start with the basics. Any single, simple operation that doesn't depend on the size of the input is considered a constant time operation, or $O(1)$.

Examples of $O(1)$ operations include:

• An assignment: int x = 5;
• An arithmetic operation: x + y
• Accessing an element in an array by its index: myArray[3]
• Pushing or popping from a stack.

Our task is to combine the complexities of these simple operations as they are organized within loops.

Rule 1: Analyzing Sequential Loops

What happens when you have two loops, one after the other? You simply add their complexities.

Consider this Java-like pseudocode:

// Assume 'n' is the size of array1 and 'm' is the size of array2
// Loop 1
for (int i = 0; i < n; i++) {
    System.out.println(array1[i]); // O(1) operation
}

// Loop 2
for (int j = 0; j < m; j++) {
    System.out.println(array2[j]); // O(1) operation
}

The first loop runs n times, so its complexity is $O(n)$. The second loop runs m times, so its complexity is $O(m)$. The total complexity is $O(n)+O(m)=O(n+m)$.

Important: If both loops ran n times, the complexity would be $O(n)+O(n)=O(2n)$. Following the rule of dropping constants from our last lesson, this simplifies to just $O(n)$.

To see this principle in action with clear code examples, please watch the first part of this video.

Rule 2: Analyzing Nested Loops

This is the most common pattern you'll encounter. When loops are nested, you multiply their complexities.

A simple nested loop looks like this:

// Assume 'n' is the length of the array
for (int i = 0; i < n; i++) {       // Outer loop runs n times
    for (int j = 0; j < n; j++) {   // Inner loop runs n times for EACH outer iteration
        // O(1) operation
    }
}

The inner loop performs $n$ operations. The outer loop executes the inner loop $n$ times. Therefore, the total number of operations is $n\times n=n^2$. The complexity is $O(n^2)$.

The following reading provides a clear, systematic breakdown of the rules for analyzing sequences and different types of loops. Think of it as your "rulebook" for this process.

Common Variations of Nested Loops

While the simple $O(n^2)$ case is common, you'll often see two important variations in interviews.

1. Different Loop Bounds: O(N * M)

If the nested loops iterate over different variables, the complexity is the product of those variables.

for (int i = 0; i < n; i++) {       // Runs n times
    for (int j = 0; j < m; j++) {   // Runs m times
        // O(1) operation
    }
}

The complexity here is $O(n\times m)$. Don't just default to $O(n^2)$. Always check the loop bounds.

2. Dependent Inner Loop: Still O(N²)

This pattern is very common in problems involving pairs of elements from an array.

for (int i = 0; i < n; i++) {
    for (int j = i; j < n; j++) {
        // Find all pairs (i, j)
    }
}

At first glance, this might seem more complex. Let's break it down:

• When i = 0, the inner loop runs n times.
• When i = 1, the inner loop runs n-1 times.
• When i = 2, the inner loop runs n-2 times.
• ...
• When i = n-1, the inner loop runs 1 time.

The total number of operations is the sum of an arithmetic series: $n+(n-1)+(n-2)+...+1$. This sum is equal to $\frac{n(n+1)}{2}=\frac{n^2+n}{2}$.

Applying our Big-O simplification rules:

1. We expand it to $\frac{1}{2}{n}^2+\frac{1}{2}n$.
2. We drop the lower-order term ($\frac{1}{2}n$), leaving $\frac{1}{2}{n}^2$.
3. We drop the constant ($\frac{1}{2}$), leaving $n^2$.

So, the final complexity is $O(n^2)$.

The next video provides an excellent visual intuition for why this triangular pattern still results in $O(n^2)$ complexity, and also covers the $O(n\times m)$ case.

Practice: Let's Analyze Some Code

Now, let's put this into practice. The best way to get comfortable with complexity analysis is to work through examples. The following video presents several short code snippets. For each one, I encourage you to:

1. Pause the video when the code appears.
2. Try to determine the time complexity yourself using the rules we've discussed.
3. Then, watch the explanation to check your understanding.

This exercise is particularly valuable because it includes a common "trick" question that interviewers sometimes use to see if you are really paying attention to the code.

Summary of Key Takeaways

You've now learned the core mechanics of analyzing iterative code. Remember these rules:

• Rule of Summation: For sequential blocks of code, add their complexities. The largest term will dominate. (e.g., $O(n)+O(n^2)=O(n^2)$).
• Rule of Multiplication: For nested loops, multiply their complexities. (e.g., An $O(n)$ loop containing an $O(m)$ loop is $O(n\times m)$).
• Count the Innermost Operations: Ultimately, you are counting how many times the most deeply nested line of code will run as a function of the input size(s).
• Read the Code Carefully: Don't just count the number of for loops. Always check the loop termination conditions. A loop might run a constant number of times, or its bounds might depend on an outer loop's variable.

In this lesson, we focused on complexities like $O(n)$ and $O(n^2)$. However, many highly efficient algorithms rely on different growth rates. In our next lesson, we will formally compare these common complexity classes and introduce logarithmic time, $O(\log n)$, which is key to understanding efficient searching and sorting algorithms.