Understanding Time Complexity: Code Patterns and Big O

A Visual Refresher

Before we dive into code, let's quickly revisit why this matters. The difference in growth rates between complexity classes is dramatic.

Your goal is to look at a piece of code and mentally map it to one of these curves to know if it's fast enough for the problem at hand.

From Counting Operations to Recognizing Patterns

At its most fundamental level, complexity analysis involves counting the number of basic operations an algorithm performs.

def f(n):
  out = 0  # 1 assignment
  for i in range(n):
    for j in range(n):
      # This block runs n*n = n^2 times
      out += i * j # 1 multiplication, 1 addition, 1 assignment (3 ops)
  return out

If we were to meticulously count, we'd find the total operations are something like 3n² + 1. Big-O notation simplifies this by focusing on the dominant term and ignoring constants. We'd say this function has a time complexity of O(n²).

While you can count operations, it's slow. The faster way is to recognize the structural patterns in the code that produce these complexities. Let's build a catalog of these patterns.

A Catalog of Common Code Patterns

We'll now go through the most common complexities, from fastest to slowest, and look at the Python code patterns that produce them.

1. O(1) — Constant Time

An algorithm is O(1) if its execution time does not change with the size of the input.

• Code Pattern: Simple arithmetic operations, variable assignments, accessing an element in an array/list by its index, or operations on a hash map (dictionary) that don't involve iteration.

# Accessing an element is O(1)
def get_first_element(data):
    if len(data) > 0:
        return data[0]
    return None

# Hash map lookups are (on average) O(1)
my_dict = {'apple': 5, 'banana': 8}
price = my_dict['apple']

2. O(log n) — Logarithmic Time

Logarithmic time complexity is incredibly efficient. It typically appears in algorithms that cut the problem size by a constant fraction in each step.

• Code Pattern: Algorithms that "divide and conquer," such as binary search. A loop where the counter is multiplied or divided by a constant factor in each iteration is also a classic sign.

The following video gives a great intuition for why "halving the problem" leads to log n complexity.

Here's a code example of that exact principle:

# This function repeatedly divides n by 2.
# The number of iterations is log base 2 of n.
def logarithmic_example(n):
    i = 1
    while i < n:
        # Instead of i += 1, we multiply. This is the key pattern.
        i *= 2 
    return i # The loop runs O(log n) times.

The most famous O(log n) algorithm is binary search, which we'll implement in a future lesson.

3. O(n) — Linear Time

This is one of the most common complexities. The runtime grows linearly with the input size n.

• Code Pattern: A single for or while loop that iterates through all n elements of a collection. Even multiple sequential (non-nested) loops still result in O(n) complexity.

The following video walks through a clear example of analyzing code with sequential loops.

The logic is: O(n) + O(n) = O(2n), and since we drop constants, it simplifies to O(n).

4. O(n log n) — Linearithmic Time

This complexity is slightly worse than linear but much better than quadratic. It's the hallmark of efficient sorting algorithms.

• Code Pattern: This often arises when you perform an O(log n) operation for each of the n items in an input. The most common real-world example is sorting. When you see list.sort() or sorted(list) in Python, you should immediately think O(n log n).

# Built-in sort is highly optimized and has an average time complexity of O(n log n).
my_list = [3, 1, 4, 1, 5, 9, 2, 6]
my_list.sort() # This line is O(n log n)

Algorithms like Merge Sort and Heapsort are classic examples that we will study later.

5. O(n²) — Quadratic Time

This complexity class is where solutions start to become too slow for larger inputs in competitive programming (e.g., for n > 10,000).

• Code Pattern: The most common pattern is a nested loop, where both the inner and outer loops iterate up to n.

Let's look at a couple of examples of this pattern.

def print_pairs(items):
    n = len(items)
    for i in range(n):
        for j in range(i + 1, n):
            print(items[i], items[j])

Beyond Polynomial Time: Recursion Patterns

Recursive functions can lead to very different complexities depending on their structure.

• A function that calls itself once: If a function of n calls itself for n-1, it often leads to O(n) complexity, as the recursion depth is n.
• A function that calls itself twice (or more): If a function of n calls itself for n-1 and n-2, this can lead to O(2ⁿ), or more generally O(cⁿ), exponential time.

This next video brilliantly contrasts these two recursive patterns using factorial and Fibonacci as examples.

Recognizing an exponential pattern is vital because O(2ⁿ) algorithms are only feasible for very small n (e.g., n < 25).

Conclusion

You now have a practical toolkit for quickly estimating the time complexity of a piece of code. This is not about precise mathematical proofs but about rapid, informed judgment—a cornerstone of success in competitive programming.

Key Takeaways & Patterns:

• O(1): Basic operations, index lookups.
• O(log n): Halving the search space (binary search), loops where the counter is multiplied/divided.
• O(n): A single loop over n elements, or multiple sequential loops.
• O(n log n): The complexity of efficient sorting (.sort()).
• O(n²): A nested loop over n elements.
• O(2ⁿ): Recursive functions with multiple self-calls that don't reduce the problem size significantly.

Up Next:

In our next lesson, we will put this knowledge to immediate use. We'll explore Python's set data structure. You'll learn how to use sets for efficient membership testing and removing duplicates. We'll see that checking if an item is in a set is an O(1) operation on average, a massive improvement over searching in a list, which is O(n). This will be your first concrete example of choosing the right data structure based on complexity analysis.