Chapter 4: Complexity Analysis

Judges usually give you only 1 second per test case. Your job is not just to solve the problem, but to solve it within that one second.

4.1 What is Time Complexity (Big O)?

We skip the formal math and just ask: how many elementary operations does the computer perform? We use O(...) to describe the worst-case magnitude.

Let N be the input size (e.g., the number of array elements):

• O(1) constant time: runtime does not change with N.

int a = v[10];
int b = n * (n + 1) / 2;

• O(N) linear: usually a single for loop. If N = 10^5, the loop runs ~100,000 times.

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

• O(N^2) quadratic: double loops.

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

⚠️ Danger: if N = 10^4, the operation count is 10^8, which already approaches the 1-second limit.

• O(log N) logarithmic: very fast—seen in binary search, set, map. Even if N = 10^{18}, log2 N is only about 60.
• O(N log N) linearithmic: the standard complexity of sort and many divide-and-conquer algorithms. It is slightly slower than O(N) but far faster than O(N^2).

4.2 Golden Rule: 1 Second ≈ 10^8 Operations

This is the most important rule in CP:

Modern judges (C++) can execute roughly 10^7 to 10^8 elementary operations in 1 second.

• Safe range: 3 ~ 5 × 10^7 operations.
• Extreme cases: 2 ~ 4 × 10^8 (may still TLE depending on constant factors).

How do you know if your algorithm will TLE? Plug the maximum N into your formula, compute the estimated operations, and check if it exceeds 10^8.

Example Exercise:

Given N = 100,000 (10^5):

1. If you write bubble sort (O(N^2)): Operation count: (10^5)^2 = 10^10. Since 10^{10} >> 10^8, it will TLE. Choose another algorithm.
2. If you use std::sort (O(N log N)): Operation count: 10^5 × log2(10^5) ≈ 10^5 × 17 ≈ 1.7 × 10^6. Since 1.7 × 10^6 < 10^8, it will pass easily.

4.3 Pick the Right Tool for the Input Size

Experts read the bounds first. Seeing the value of N, you can guess which algorithm the setter expects.

💡 Memory tip: when you see N = 10^5, no matter how weird the problem looks, the safe bets are sorting, binary search, or a linear greedy solution.

4.4 Space Complexity: Avoid Exploding Memory

Besides the time limit, there is a memory limit (usually 128MB or 256MB).

How to estimate? Look at how large your arrays are.

• int: 4 bytes
• long long: 8 bytes
• char: 1 byte

Conversion reminder: 1 MB ≈ 10^6 bytes 256 MB ≈ 2.5 × 10^8 bytes

If you declare int a[N]:

• N = 10^6: uses 4 MB → very safe
• N = 10^7: 40 MB → safe
• N = 10^8: 400 MB → dangerous! You might hit MLE (Memory Limit Exceeded)

⚠️ Global vs local: Declare large arrays outside main (global scope). Local arrays live on the stack, which typically has only a few megabytes. Large stack allocations cause stack overflow failures.

4.5 Micro-optimizations (The Constant Factor Game)

Sometimes the complexity is correct but your solution still TLEs because the constant is too big.

1. I/O: Always add ios::sync_with_stdio(0); cin.tie(0); (see Chapter 2).
2. Modulo: Avoid excessive % operations—they are slow.
3. Bit operations: Multiply by 2 with << 1, divide by 2 with >> 1, test parity with & 1. Modern compilers optimize, but manual bit tricks still help in tight scenarios.
4. endl vs \n: Never use endl inside loops. It flushes the buffer and is much slower. Prefer \n.

🧠 Chapter Recap & Exercises

Core idea: before writing code, check N, compute O, then decide on a strategy.

Thought exercise: Suppose a problem gives you N points.

1. If N = 5000, can you compute the distance between every pair with double loops? (Operations: 2.5 × 10^7 → yes.)
2. If N = 200,000, are double loops still feasible? (Operations: 4 × 10^{10} → no. You must find an O(N log N) or O(N) solution.)

Once you can eyeball the constraints, the next chapter will show you how to elegantly apply brute-force tactics—the simplest strategies that still score points.