I've spent a lot of time in code reviews spotting a specific pattern: a developer writes a piece of logic that works perfectly with 10 items in a test list, but completely freezes the production server when that list grows to 10,000. This is usually because they aren't thinking in terms of Big-O notation. Now, "Big-O" sounds like academic jargon from a computer science lecture, but in practice, it's just a way for us to describe how a piece of code slows down as the input gets bigger.

The "Just Loop Through It" Trap

Let's look at a common task: checking if a list of usernames contains any duplicates. When you're first starting out, the most intuitive way to do this is to pick the first name, compare it to everything else, then pick the second name and compare it to everything else, and so on. It looks like this:

public bool HasDuplicatesNaive(List<string> usernames)
{
    for (int i = 0; i < usernames.Count; i++)
    {
        for (int j = i + 1; j < usernames.Count; j++)
        {
            if (usernames[i] == usernames[j]) return true;
        }
    }
    return false;
}

This works, but it's what we call $O(n^2)$, or "quadratic time." If you have 10 names, you're doing roughly 100 comparisons. Not a big deal. But if you have 100,000 names, you're suddenly looking at 10 billion operations. Your CPU will be screaming, and your users will be refreshing their browsers in frustration. The cost here grows quadratically relative to the input size.

Trading Memory for Speed

To fix this, we have to change our strategy. Instead of comparing every item to every other item, we can use a HashSet. A HashSet uses a hash table internally, which allows us to check if an item already exists almost instantaneously, regardless of how many items are already in the set.

public bool HasDuplicatesEfficient(List<string> usernames)
{
    var seen = new HashSet<string>();
    foreach (var name in usernames)
    {
        // .Add returns false if the item was already present
        if (!seen.Add(name)) return true; 
    }
    return false;
}

This version is $O(n)$, or "linear time." If you have 100,000 names, you do roughly 100,000 operations. That's a massive difference—we went from billions of operations to thousands. However, there is a trade-off. The naive version used almost no extra memory (it just used two integer counters). The HashSet version uses $O(n)$ space because it has to store every name it encounters. In the professional world, we almost always trade memory for speed, because RAM is cheap but user patience is expensive.

Thinking in Growth, Not Seconds

One thing that trips people up is trying to measure Big-O with a stopwatch. Don't do that. Hardware varies; a fast M3 chip will run $O(n^2)$ code faster than an old laptop, but the growth curve remains the same. When I talk about Big-O, I'm talking about the shape of the line on a graph.

• $O(1)$ - Constant Time: Accessing an element in an array by index. It takes the same time whether the array has 1 item or 1 million.
• $O(n)$ - Linear Time: A single foreach loop through a list. If the list doubles, the time doubles.
• $O(n \log n)$ - Linearithmic Time: This is the typical cost of a good sorting algorithm (like Array.Sort() in C#).
• $O(n^2)$ - Quadratic Time: Nested loops where both loops iterate over the same collection. This is the danger zone.

Whenever you write a loop, I want you to ask yourself: "What happens to this code if the input size increases by a thousand?" If the answer is "it'll probably be fine," you're likely in linear territory. If the answer is "it might actually crash the app," you've probably accidentally written a quadratic algorithm.

📋 Practical Task

Exercise: Optimizing a User Permission Checker

You've been handed a legacy method that checks if a user has any of the "Required Permissions" for a specific admin page. The current implementation is incredibly slow because it uses nested loops to compare a user's assigned roles against a list of required permissions.

Your Task: Rewrite the HasRequiredPermission method to improve its time complexity from $O(n * m)$ to $O(n + m)$ using a HashSet. Ensure the method still returns true if there is at least one overlap between the two lists.

public class PermissionService
{
    // NAIVE IMPLEMENTATION - Optimize this!
    public bool HasRequiredPermission(List<string> userRoles, List<string> requiredPermissions)
    {
        foreach (var role in userRoles)
        {
            foreach (var permission in requiredPermissions)
            {
                if (role == permission)
                {
                    return true;
                }
            }
        }
        return false;
    }
}