01. Time Complexity

What you'll learn

• 1Explain Big-O notation and the main complexity classes
• 2Analyze the time complexity of code snippets
• 3Pick the right algorithmic approach for a given input size N

Overview

Solving an algorithm problem isn't just about getting the right answer — it has to be fast enough. Most BOJ problems have a 1–2 second time limit and 128–256 MB memory limit. Inefficient algorithms fail to pass. Mastering Big-O lets you predict whether your approach will succeed before you ever write the code.

Core Concepts

1. What is Big-O?

Big-O expresses how an algorithm's running time (or memory) grows as the input size N gets very large, in the worst case. We drop constants and lower-order terms.

Example: 3n² + 5n + 7 → O(n²)

2. Common complexity classes

3. Time limits and operation count

4. Memory limits

In Python, a list of 1,000,000 integers takes roughly 8 MB (C/C++ uses ~4 MB). Python object overhead is significant — about 28 bytes per int — so be more conservative than with C++.

List of N ints:           ~8N bytes (with Python overhead per element)
2D list (N × N):          O(N²) space → N=1000 needs ~8 MB

5. Measuring real time with timeit

import timeit

# Quick snippet timing
result = timeit.timeit('sum(range(1000))', number=10000)
print(f'10,000 iterations took {result:.4f}s')

# Larger blocks: time.perf_counter
import time
start = time.perf_counter()
# ... code under test ...
print(f'Elapsed: {time.perf_counter() - start:.6f}s')

Examples

Example 1: Visualize complexity classes — src/01_big_o_demo.py

Print the actual operation counts of each Big-O class from O(1) up to O(n²).

[Sample output]
O(1)     ops:            1  (n=100000)
O(log n) ops:           17  (n=100000)
O(n)     ops:       100000  (n=100000)
O(n²)    ops:       499500  (n=1000)
O(2ⁿ)    ops:      1048576  (n=20)

Example 2: Actual timing — src/02_time_measure.py

Compare bubble sort O(n²) with Python's built-in sorted() O(n log n) across input sizes.

[Sample output]
Size      Bubble (s)    sorted() (s)   Ratio
  100       0.001234      0.000023     53.7x
 1000       0.125600      0.000310    405.2x
10000      12.340000      0.003500   3525.7x

Example 3: Space complexity — src/03_space_complexity.py

Use sys.getsizeof to measure O(1) / O(n) / O(n²) space usage of different data structures.

Example 4: Linear vs Binary Search — src/04_complexity_compare.py

Count comparisons performed by linear search (O(n)) versus binary search (O(log n)) on the same data.

Common Mistakes

1. Applying an O(n²) solution to N=100,000 → ~10¹⁰ operations → guaranteed TLE. Check N before writing a nested loop.
2. Forgetting Python is 5–10× slower than C++. Even an O(n log n) solution may need PyPy to pass.
3. Ignoring large constants. String concatenation in a loop with += looks O(n) but is actually O(n²).
4. Using `in` on a list (O(n)) instead of a set (O(1) avg) for membership checks.
5. Submitting without doing complexity analysis first. Always compute 'this approach is O(?) at N=?' before coding.

Recap

• Big-O describes worst-case growth.
• Use 1 second ≈ 10⁸ operations as your guide.
• Python is slower than C++ — sometimes you need a tighter algorithm.
• The right data structure can change O(n) into O(1).

Try It

1. Run src/01_big_o_demo.py with n=100 and record operation counts.
2. Run src/02_time_measure.py at n=100,000 (bubble sort will be very slow — that's the point).
3. Solve BOJ 1546 (Average) and write out the time complexity of your solution.
4. Complete the exercises in homework/README.md.