~/journaleaf
← cd ..

6 min read

Choosing an Algorithm by Time Complexity: Input-Size Limits and Python Measurements

#algorithm-basics#python#time-complexity

The first thing to do on a coding-interview problem is not to write code but to read the input size N and decide which time complexity can pass. If that judgment is wrong, even a correct solution times out. This post gives a reference table, then checks it by running Python code.

The yardstick: about 10 million operations

For problems with a one-to-two-second limit, the convention is that Python can safely handle roughly 10 million operations. The exact figure depends on the judge and on what each operation does, so I first timed a plain loop in this environment (Python 3.9.6, Apple Silicon Mac).

pythonoriginal

What the code does: loop(n) adds up the numbers 0 to n-1, which is about the cheapest loop body Python can run. timeit.repeat calls it three times with n = 10 million, and min keeps the fastest run because slower runs mostly reflect other programs on the machine.

Ten million iterations took about 0.19 seconds, roughly 50 million per second. A real loop body mixes list access, comparisons and function calls and costs far more per iteration, which is why "10 million simple operations" is a conservative ceiling.

Reference table by input size

The table is built so that the operation count at the upper bound of N is close to 10 million.

Input size NComplexity that passesApproximate operations
up to 20O(2^N) brute forceabout 1 million
up to 200O(N^3)8 million
up to 3,000O(N^2)9 million
up to 500,000O(N log N)about 9.5 million
up to 10,000,000O(N)10 million
largerO(log N) or a formula-

This is a convention, so if the loop body is heavy, move down one row. For a feel of O(N log N), Python's built-in sorted took 139.2 ms here to sort one million random integers; calling sort N times inside a loop is the real danger.

Measurement 1: duplicate check, O(N^2) vs O(N)

Two ways to check whether a list contains a duplicate. The worst case is a list with no duplicates, so that is the input I timed.

pythonoriginal

What the code does: has_dup_quadratic compares every pair of elements with two nested loops, about n²/2 comparisons, and returns early only when it finds a match. has_dup_set builds a set, which drops repeated values, and compares sizes: if the set is smaller than the list, something was duplicated. The demo list has no duplicates, so the nested loops cannot exit early.

Best of three runs:

nNested loopsGrowthset version
5003.04 ms-0.0035 ms
1,00011.47 ms3.8x0.0050 ms
2,00046.70 ms4.1x0.0108 ms
4,000186.25 ms4.0x0.0211 ms

Each time n doubles, the nested loops take about four times as long: the shape of O(N^2). Extrapolating, n = 100,000 is 25 times larger than n = 4,000, so the time would be 625 times longer, about 116 seconds (an estimate). That is why the table allows O(N^2) only up to about 3,000.

The set version grew from 0.0035 ms to 0.0211 ms while n grew eightfold, roughly proportional to N. Since building a set runs in C, compare growth patterns rather than the raw gap.

Measurement 2: x in list is O(N)

Inside a loop, if x in lst looks like one line but costs N. I timed the worst case, where the value is absent. The snippet is a small version you can edit (try a bigger n); the table was measured with more repetitions.

pythonoriginal

What the code does: it builds the same numbers as a list and as a set, then times x in ... for a value that is not present, so the list has to scan every element before answering. Each total is divided by its repetition count to get the time per lookup; the set gets far more repetitions because a single lookup is too fast to time reliably.

nList, per lookupSet, per lookup
1,0004.42 µs0.0336 µs
10,00044.79 µs0.0320 µs
100,000457.65 µs0.0287 µs
1,000,0004,654.09 µs0.0341 µs

While n grew 1,000x, the list lookup grew from 4.42 µs to 4,654 µs (about 1,050x) and the set lookup stayed near 0.03 µs. So a loop that runs N times and contains in list is really O(N^2) even though it reads like O(N).

The price of speed: memory

Sets are not free. A hash table keeps empty slots on purpose, so it uses more memory than a list for the same elements. For one million integers, sys.getsizeof reported about 8.0 MB for the list and 33.6 MB for the set, 4.2 times as much (the integer objects themselves are excluded, since they are the same either way). When the memory limit is tight, space matters as much as time.

What to check when you get a time-limit error

If the solution is correct but too slow, go through this in order:

  1. Re-read the range of N and check whether your complexity fits the table.
  2. Count the nested loops. Two levels with N = 100,000 means you need a different algorithm.
  3. Look for hidden O(N) work inside loops: in list, list slicing, sorting on every iteration.
  4. Only then tune constants such as input reading. That cannot rescue the wrong complexity.

Summary

Read N first, use the table to rule out anything too slow, and hunt for hidden O(N) work inside loops. The numbers above come from Python 3.9.6 on macOS (Apple Silicon) and vary between runs; what does not change is the growth pattern, meaning how many times longer it takes when n doubles.

The next post turns in list into a hash map and cuts a classic O(N^2) solution to O(N).