I’ve sat through countless technical interviews where candidates tell me, "This function is O(n) because it takes about 10 milliseconds to run on my machine." This is the single most common trap learners fall into: treating Big-O as a measurement of time.

Stop treating Big-O like a stopwatch

If you think Big-O is about seconds or milliseconds, you're measuring the wrong thing. Clock time is a lie. It depends on whether you're running on a 10-year-old laptop or a high-end Threadripper; it depends on whether your OS decided to run a background update while your code was executing. Big-O isn't about the clock; it's about the trend.

Consider these two snippets. The first is a simple linear search, and the second is a nested loop searching for pairs. If you run these with an array of only 3 elements, the nested loop might actually finish "faster" in raw clock time because of how the CPU caches small chunks of memory. But that's a fluke of small numbers.

// Snippet A: Linear Search
for (int i = 0; i < n; i++) {
    if (arr[i] == target) return i;
}

// Snippet B: Nested Pair Search
for (int i = 0; i < n; i++) {
    for (int j = i + 1; j < n; j++) {
        if (arr[i] + arr[j] == target) return 1;
    }
}

When $n$ is 3, Snippet A does 3 operations and Snippet B does 3. No big deal. But when $n$ is 100,000? Snippet A does 100,000 operations. Snippet B does roughly 5 billion. No amount of overclocking your CPU will bridge the gap between a linear growth and a quadratic growth.

Focusing on growth, not clock time

Big-O analysis is about describing how the requirements of your algorithm grow as the input size ($n$) grows. I like to think of it as "scaling behavior." We ignore constants because they don't change the shape of the growth curve. If your loop does three assignments instead of one inside the body, it's still $O(n)$. The "slope" is steeper, but it's still a straight line.

• O(1) - Constant Time: Accessing an array element by index. It takes the same amount of time whether the array has 10 elements or 10 million.
• O(log n) - Logarithmic Time: Binary search. Every time you perform an operation, you cut the remaining work in half. This is the gold standard for searching large datasets.
• O(n) - Linear Time: A single loop through an array. If the input doubles, the time doubles.
• O(n²) - Quadratic Time: Nested loops. If the input doubles, the time quadruples. This is where C programs usually start to feel "laggy."

Spotting patterns in your C loops

In C, you can usually determine the Big-O just by looking at your loop structures. If you see a loop that increments by 1 and goes from $0$ to $n$, you're looking at $O(n)$. If that loop is inside another loop that also goes from $0$ to $n$, you've hit $O(n^2)$.

But watch out for loops that don't increment linearly. If you see something like for (int i = 1; i < n; i *= 2), that's a huge hint that you're dealing with $O(\log n)$. The variable $i$ is growing exponentially, which means the number of iterations is growing logarithmically relative to $n$.

When the "constant" actually matters

Now, I'll give you a bit of a professional secret: while we ignore constants in theoretical Big-O, in the real world of C programming, constants do matter. C is chosen for performance. An $O(n)$ algorithm with a massive constant (like doing a heavy disk I/O operation inside the loop) might be slower in practice than an $O(n^2)$ algorithm with a tiny constant for small $n$.

However, never use that as an excuse to write inefficient algorithms. The "constant" advantage vanishes the moment your data scales. Always optimize for the growth rate first, then tune the constants.

📋 Practical Task

Analyzing and Optimizing a Naive Duplicate Finder

You have been handed a piece of legacy C code that checks if an array contains any duplicate integers. The current implementation is naive and slow. Your task is to analyze its complexity and then implement a more efficient version.

#include <stdio.h>
#include <stdbool.h>

bool has_duplicates_naive(int arr[], int n) {
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            if (arr[i] == arr[j]) return true;
        }
    }
    return false;
}

Your requirements:

1. Identify the Big-O complexity of the has_duplicates_naive function.
2. Write a new function has_duplicates_optimized. To do this, you may assume the array is already sorted (or you may sort it using qsort from <stdlib.h>).
3. The optimized version must have a better Big-O complexity than the naive version.
4. Create a main function to test both versions with a large array (e.g., 10,000 elements) to observe the difference in execution time.