Big-O: how engineers talk about speed

Big-O, how engineers talk about speed

Two correct solutions to the same problem can differ so much in speed that one finishes in a millisecond and the other outlives the interview.

Engineers need a way to compare algorithms before running them, one that does not depend on whose laptop is faster. Interviewers also ask for it by name in nearly every technical interview, and this unit's patterns only make sense with it, so it comes first.

The time complexity of a piece of code is how the number of basic steps it performs grows as its input size grows. Input size is written n, meaning the length of the string or the number of elements in the array.

Big-O notation summarizes that growth by keeping only the dominant trend and dropping constant factors. A loop that does 3n + 5 steps is written O(n), read as "order n", because for large n the tripling and the extra 5 stop mattering next to the shape of the curve.

Code like that is called linear: double the input and you double the work. The point of throwing away the constants is that they depend on the machine, while the shape does not.

The classes you will actually meet

The last column is why complexity matters. At a million elements the gap between O(n) and O(n²) is the gap between instant and going out for lunch.

When one algorithm's big-O beats another's, we say it is asymptotically faster, meaning faster in the trend as n grows, whatever the constant factors do on small inputs.

Two reading rules cover most code you will analyze:

• Steps in sequence add, and the biggest term wins, so a pass followed by another pass is O(n) plus O(n), which is O(n).
• Nesting multiplies, so a full inner loop per outer pass is n × n, which is O(n²).

One refinement shows up immediately. An operation is O(1) amortized when its cost averages out to constant over many calls even though a rare individual call is expensive. ArrayList.add is the classic case, since it occasionally must copy everything into a bigger internal array, an O(n) moment, but that happens so rarely that n adds still cost O(n) in total, meaning O(1) each on average.

Counting steps in two loop shapes

The same n, one flat loop and one nested loop.

public class Main {
  public static void main(String[] args) {
    int n = 1000;

    int linear = 0;
    for (int i = 0; i < n; i++) {
      linear++;
    }

    int quadratic = 0;
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < n; j++) {
        quadratic++;
      }
    }

    System.out.println("n = " + n);
    System.out.println("O(n) loop steps: " + linear);
    System.out.println("O(n^2) loop steps: " + quadratic);
  }
}

Output

n = 1000
O(n) loop steps: 1000
O(n^2) loop steps: 1000000

One thousand steps against one million, from source code that differs by a single nested loop. The nested version does a full inner sweep for every outer pass, which is the multiplication rule made visible.

At n = 2000 the linear count doubles to 2000 while the quadratic count quadruples to 4,000,000. That different response to a doubled input is exactly what the notation is describing.

A constant-time call inside a loop

A method that loops over an array once and calls stock.containsKey(...) on a HashMap inside that loop, an O(1) operation, is O(n) overall.

Nesting multiplies, and here it is n iterations times O(1) work each, which is O(n).

That contrast is precisely why HashMaps appear in so many interview solutions. They let you keep a lookup inside a loop without paying the loop-in-a-loop O(n²) that scanning a list would cost.

The lesson generalizes past maps. When a loop is unavoidable, the useful question is what the cheapest possible body is, since the loop multiplies whatever that body costs.

The cost of a quadratic pass at n = 10,000

Checking every pair in a 10,000-element array with two nested loops is O(n²), which is 10,000² and therefore about 100,000,000 steps.

A modern CPU survives 100 million simple steps in well under a second when it happens once. Inside a server handling thousands of requests it is a fire, because the same work repeats per request.

The scaling is the danger rather than the current number. Data that grows by a factor of 100 makes a quadratic solution 10,000 times slower, so code that was fine in testing dies in production.

The interview move is to name it out loud, saying that a solution is O(n²) and that a HashMap or a sort can do better, which is what the next lessons practice.