What is Complexity?

Why Do We Care?

In competitive programming, getting the correct answer is not enough — your solution must also run fast enough. Complexity analysis is how we predict whether our code will pass within the time limit before we even submit it.

Rule of Thumb

A modern computer can execute roughly 10⁸ simple operations per second. If the time limit is 1 second and n ≤ 10⁵, an O(n²) solution does 10¹⁰ operations — too slow. An O(n log n) solution does ~1.7 × 10⁶ — fast enough.

Big-O Notation

Big-O describes the upper bound of how an algorithm's runtime grows relative to its input size n. We always focus on the dominant term and drop constants.

// O(1) — Constant: doesn't depend on n
int x = arr[0];

// O(n) — Linear: one loop over n
for (int i = 0; i < n; i++) { ... }

// O(n²) — Quadratic: nested loops
for (int i = 0; i < n; i++)
    for (int j = 0; j < n; j++) { ... }

// O(log n) — Logarithmic: halving each step
while (n > 0) { n /= 2; }

// O(n log n) — Linearithmic: e.g. sorting
sort(arr, arr + n);

Common Complexities Ranked

Complexity	Name	n = 10⁶	Verdict
O(1)	Constant	1	✓ Fast
O(log n)	Logarithmic	~20	✓ Fast
O(√n)	Square Root	~1000	✓ Fast
O(n)	Linear	10⁶	✓ Fast
O(n log n)	Linearithmic	~2 × 10⁷	✓ Fast
O(n²)	Quadratic	10¹²	✗ TLE
O(2ⁿ)	Exponential	🤯	✗ TLE

Estimating from Constraints

Before writing code, check the constraint on n in the problem. This tells you the maximum complexity your solution can have:

n ≤ 10O(n!) or O(2ⁿ)

n ≤ 20O(2ⁿ)

n ≤ 500O(n³)

n ≤ 5000O(n²)

n ≤ 10⁶O(n log n)

n ≤ 10⁸O(n)

Counting Operations — Example

// What is the complexity of this?
int count = 0;
for (int i = 0; i < n; i++)          // runs n times
    for (int j = i; j < n; j++)      // runs n-i times
        count++;

// Total = n + (n-1) + (n-2) + ... + 1
//       = n(n+1)/2
//       = O(n²)  ← drop constants & lower terms

Common Mistake

Don't confuse j = i with j = 0 — the inner loop starting at i still gives O(n²), just with half the operations. Big-O ignores constant factors.