Theoretical runtime analysis of Big O notation

Big O notation describes the order of growth — how the running time changes as the input grows. Here is a small thought experiment in Go that takes that definition completely literally, and ends up somewhere absurd. The absurdity is the point.

A linear loop

func example(n int) int {
	var res int
	res = 0
	for i := 0; i < n; i++ {
		res++
	}
	return res
}

This is $O(n)$: the loop runs n times, so the work scales with the input.

$n\times O(1)=O(n)$

Making it "constant"

Now suppose the problem statement guarantees $n\leq10^9$. Rewrite the loop to count to that fixed bound and break out early:

func example(c int) int {
	var res int
	res = 0
	for i := 0; i <= 1000000000; i++ {
		res++
		if i >= c {
			break
		}
	}
	return res
}

The loop bound is now a literal. It cannot run more than $10^9+1$ times no matter what you pass in. A loop whose trip count is bounded by a constant does a constant amount of work, so by the definition:

$c\times O(1)=O(1)$

The function is $O(1)$. Nothing about this is a trick of notation — it follows directly from what the notation says.

Why it works, and why it is empty

The same move generalises. A quadratic solution on a graph with $N\leq2\times10^5$ nodes becomes "constant time" if you loop to $2\times10^5$ and ignore the excess. So does a cubic one. So does an exponential one.

That should be suspicious, and it points at the real lesson: Big O is only meaningful over an unbounded input domain. Once the input is capped by a constant, every terminating algorithm is $O(1)$, because the whole input space is finite and you can bound the work by its worst case. The claim is true and completely uninformative.

$\text{bounded input} \implies \text{every terminating algorithm is } O(1)$

This is why complexity is stated in terms of $n$ growing without limit, and why in practice we care about the growth rate rather than the constant. Two algorithms that are both technically $O(1)$ on the same bounded input can differ by a factor of a billion, and that factor is the only thing your users will notice.

The takeaway

When you see a complexity claim, check what is being held fixed. "$O(1)$ because the input is bounded" is a sentence that is true of every program ever written, which makes it worth exactly nothing. The useful question was never what is the complexity — it is how does the work grow when the input does.