Big-O Complexity of Iterative Code

Welcome back! In our last lesson, we explored the "what" and "why" of Big-O notation, getting familiar with the most common complexity classes like O(n) and O(n²). We learned to compare them and understand their performance implications at a high level.

Today, we shift our focus to the "how." The goal of this lesson is to give you a systematic process for analyzing simple iterative C code and determining its time complexity yourself. We will move from looking at graphs to looking at for loops and if statements, transforming theory into a practical skill for evaluating your own code.

The Rules of Combination

Before we dive into loops, let's establish some ground rules for how to combine the complexities of different parts of a program. A piece of code is rarely just one single loop; it's often a sequence of operations or contains conditional branches.

This short video from GeeksforGeeks clearly explains the two main rules we need: one for sequential statements and one for conditional statements.

To summarize these rules:

• Rule 1: Add for Sequence. If you have two parts of a program that run one after the other, their total complexity is the sum of their individual complexities. Because we only care about the dominant term in Big-O, this simplifies to just the complexity of the "slower" part. For example, an O(n) loop followed by an O(n²) loop results in an overall complexity of O(n²).
  $O(n)+O(n^2)=O(n^2)$
• Rule 2: Take the Max for Branches. For an if-else block, the overall complexity is determined by the path that does the most work. If the if block is O(n) and the else block is O(1), the complexity of the entire structure is considered O(n).

With these rules in hand, let's start analyzing loops.

Analyzing Single Loops: Linear Time

The most common structure you'll analyze is a single loop that iterates over a collection of n items.

As we learned in the last lesson, if a loop runs n times and the work done inside the loop is constant (O(1)), the total time complexity is n * O(1), which simplifies to O(n).

What if the loop doesn't just increment by one? Let's see how different loop structures are analyzed.

The key insight from the video is that constant factors don't matter. A loop that runs n/2 times or n/20 times still grows linearly with n. As n gets very large, the line on the graph still goes up in a straight line, just at a different angle. In Big-O notation, we drop the constant factor, so all these variations are simplified to O(n).

For example:

// This function sums the elements of an array.
// The loop runs 'size' times.
// Complexity: O(n) where n is 'size'.
int sum_array(int arr[], int size) {
    int total = 0;              // O(1)
    for (int i = 0; i < size; i++) { // Loop runs n times
        total += arr[i];        // O(1) work inside
    }
    return total;               // O(1)
}
// Total: O(1) + O(n) + O(1) = O(n)

Analyzing Nested Loops: Quadratic Time

Things get more interesting when we nest loops inside one another. This is a very common pattern that often leads to quadratic, O(n²), complexity.

Case 1: Independent Nested Loops

The simplest case is when the inner loop's iterations are independent of the outer loop. In this scenario, for every single one of the outer loop's n iterations, the inner loop also runs n times.

The rule is simple: multiply the complexities of the loops.

// O(n) * O(n) = O(n^2)
void print_pairs(int n) {
    // Outer loop runs n times
    for (int i = 0; i < n; i++) {
        // Inner loop runs n times for EACH outer iteration
        for (int j = 0; j < n; j++) {
            printf("(%d, %d)\n", i, j); // O(1) work
        }
    }
}

The total number of print statements executed will be $n\times n=n^2$.

Case 2: Dependent Nested Loops

A slightly more complex case is when the inner loop's number of iterations depends on the outer loop's current variable. A classic example is printing a triangular pattern.

void print_triangular_pairs(int n) {
    // Outer loop runs n times
    for (int i = 0; i < n; i++) {
        // Inner loop's iterations depend on 'i'
        for (int j = 0; j < i; j++) {
            printf("(%d, %d)\n", i, j);
        }
    }
}

Here, we can't just multiply n * n. Let's trace the work:

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

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

Applying our simplification rules (drop constants and lower-order terms), this expression simplifies to O(n²).

Let's watch a detailed trace of this exact scenario.

For a more formal, text-based breakdown of this "add when you can't multiply" principle, the following guide is excellent.

A Final Challenge: Thinking About the Condition

So far, our loops have had simple counters (i++). But the complexity is really determined by how many steps it takes for the loop's condition to become false. Let's look at one final, less obvious example.

void complex_loop(int n) {
    int p = 0;
    for (int i = 1; p <= n; i++) {
        p = p + i;
        // some O(1) operation
    }
}

How many times does this loop run? It's not n times. The loop stops when p, the sum of 1 + 2 + 3 + ... + i, becomes greater than n. This is the same arithmetic series we just saw! The loop stops when $\frac{i(i+1)}{2}>n$, which is approximately when $i^2\approx n$, or $i\approx \sqrt{n}$. Therefore, the complexity is O(√n).

This type of analysis is crucial because it forces you to look beyond simple counter iteration and think about what condition is actually terminating the loop.

Let's watch this final example being analyzed.

Conclusion

In this lesson, we transitioned from identifying complexity classes to calculating them for simple iterative code. You now have a practical toolkit for analyzing loops and conditionals.

Key Takeaways:

• Analyze Systematically: Break code down into sequential, conditional, and looped blocks.
• Add for Sequence: For sequential code, add complexities and keep the dominant term (e.g., O(n) + O(n²) = O(n²)).
• Take Max for Branches: For if-else statements, use the complexity of the worst-case (slowest) branch.
• Multiply for Independent Loops: The complexity of independent nested loops is the product of their individual complexities (e.g., O(n) * O(n) = O(n²)).
• Sum for Dependent Loops: For loops where the work per iteration changes (like the triangular pattern), sum the work across all iterations. This often still results in O(n²).
• Focus on the Condition: The true complexity is determined by how many steps it takes for the loop's termination condition to be met, which can lead to less obvious complexities like O(√n) or O(log n).

Preview of the Next Lesson:
We've consistently used the term "worst-case" when analyzing if-else blocks and certain loops. In the next lesson, we will formalize this concept by exploring the differences between best-case, worst-case, and average-case analysis. This will add more nuance to our understanding of algorithm performance.