Reading Constraints to Choose an Approach

The practical version

Big O notation gets taught as theory. In a contest it is a decision tool: you read the maximum input size, and it tells you which approaches can possibly pass. Getting this right before writing code is the difference between four hours well spent and four hours spent optimizing something that was never going to work.

The judge gives you a time limit, typically two seconds for Java. A rough working estimate is that you can perform around 10⁸ simple operations per second. This is imprecise — the real number depends on what the operations are — but it is accurate enough to choose an approach.

The table to memorize

What fits in the time limit

This table is the most useful thing in this module. The input size is not decoration in the problem statement — it is the problem telling you what it wants.

Counting operations

To find the complexity, count how many times the innermost work runs as a function of the input size.

// O(N) — the loop body runs n times
long sum = 0;
for (int i = 0; i < n; i++) {
    sum += a[i];
}

// O(N^2) — for each i, the inner loop runs up to n times
int best = 0;
for (int i = 0; i < n; i++) {
    for (int j = i + 1; j < n; j++) {
        best = Math.max(best, a[i] + a[j]);
    }
}

The second example runs about N²/2 times, not N². Big O drops the constant factor, so both are O(N²). That is usually the right call, but not always — see the caveat below.

// O(N log N) — sorting dominates the linear scan after it
Arrays.sort(a);
for (int i = 0; i < n; i++) {
    // constant work
}

Where the log comes from

A log N factor appears when something repeatedly halves the search space or when you use a balanced tree structure.

Common operations and their cost

For N = 200,000, log N is about 18. So O(N log N) is roughly 3.6 million operations — comfortable. O(N²) is 4 × 10¹⁰ — hopeless. That gap is the single most important boundary in intermediate and advanced problems.

Space matters too

Memory limits are usually 256 MB. Java’s overhead is higher than C++’s, so it is worth a quick check.

The last two points are Java-specific and catch people who are used to C++ memory estimates. When keys are bounded integers, an array is both faster and much smaller than a map.

When constants actually matter

Big O hides constant factors, and occasionally the constant decides the outcome. Two O(N log N) solutions can differ by a factor of ten if one allocates objects in the inner loop and the other does not.

There is one genuine correctness caveat to Arrays.sort on primitives: its quicksort can be driven to O(N²) by adversarial input. This is rare in practice but real in some contests. If you are worried, sort boxed Integer[] (merge sort, guaranteed O(N log N)) or shuffle the array before sorting.

Worked example

A problem gives N ≤ 100,000 integers and asks whether any two of them sum to a target X.

The direct approach is to check every pair: O(N²) = 10¹⁰. Too slow.

Consulting the table, N ≤ 100,000 allows O(N log N) or O(N). Two approaches fit:

// O(N) average — one pass with a hash set
Set<Integer> seen = new HashSet<>();
boolean found = false;
for (int i = 0; i < n; i++) {
    if (seen.contains(x - a[i])) {
        found = true;
        break;
    }
    seen.add(a[i]);
}

// O(N log N) — sort, then two pointers from both ends
Arrays.sort(a);
int lo = 0, hi = n - 1;
boolean found = false;
while (lo < hi) {
    int sum = a[lo] + a[hi];
    if (sum == x) { found = true; break; }
    else if (sum < x) lo++;
    else hi--;
}

Both pass. The point is that the constraint told you to look for one of them instead of submitting the nested loop.

Related