Complexity from measurements

How many times longer does it take to multiply two numbers if each is twice as long? By the school rule, four times: each digit of one number is multiplied by each digit of the other. Python, on numbers of hundreds of thousands of bits, answers differently: three times. On logarithmic axes the time falls on a straight line with a slope of about 1.58, and log₂ 3 ≈ 1.585 is the trace of Karatsuba's algorithm, about which the program says not a word. Below are seven operations measured in Python and Go. Guess how each grows and check by the slope and by the table under the graph.

The number above each segment is its slope: by how much the time grew, written as a power of the growth of n. The slopes of neighbouring segments jump about, and one segment cannot be trusted. The table below the graph does something else: it divides the time by six candidates and shows which quotient hardly changes. Try “Multiplication: repeats” in Python and in Go: a trap is hidden there, one that the first version of the measurement for this article fell into.

The idea

If the time grows as c·n^k, then ln T = ln c + k·ln n: on axes where both are logarithms, this is a straight line, and its slope is the exponent k. The factor c, the speed of the machine and the language, only shifts the line up or down. That is why Python and Go in the scene give one slope for multiplication while differing several times in time: the exponent belongs to the algorithm. The slope of the segment between two measurements is

$$k_{12} = \frac{\ln(T_2/T_1)}{\ln(n_2/n_1)},$$

and the doubling test from the article on big O and the course chapter is its special case: with n₂ = 2n₁ it is just log₂ of the ratio of the times.

The slope suggests which candidate to start with, but it does not make the diagnosis. The ratio test does: the time is divided by a candidate, n, n log n, n², 2ⁿ, and the quotient is watched at large n. For the right candidate it is almost constant, for a wrong one it creeps up or down. Exponentials are checked on semi-logarithmic axes: there they are straight lines.

The slope: what it knows and what it does not

A power has the same slope at all n. Other functions have their own at each point, and it is useful to understand this in advance.

Three consequences follow, and all are visible in the scene.

n log n looks like n^1.1. At a thousand elements the slope of n log n is 1.14, at a million 1.07, and it is exactly 1.1 at n = e¹⁰ ≈ 22,000. The logarithmic factor hides in tenths of the slope, and rounding erases it: sorting “grows linearly”. Sedgewick and Wayne's algorithms course says it plainly: the doubling test does not distinguish logarithmic factors.

An exponential is not a straight line. The slope of 2ⁿ grows with n, and on log-log axes the graph gets steeper and steeper, like “Subsets”. But on semi-logarithmic axes, where only the time is a logarithm, ln 2ⁿ = n ln 2 is a straight line. Its slope is the logarithm of the factor per step: n one larger, the time twice as long. And n! bends upwards even there: the ratio n!/(n − 1)! = n grows, which is worse than any exponential.

One segment is two measurements and their noise. If each measurement is off by 10 %, the slope of the segment between n and 2n may be off by ±0.3: log₂(1.1/0.9) ≈ 0.29. The slope over many points is more reliable, and most reliable of all is what checks the shape as a whole.

When n log n cannot be told from a power

How alike are n log n and n^1.1? Choose the factor c so that c·n^1.1 runs as close as possible to n log n on a chosen range, and see how far apart they get. Move the ends of the range and the exponent.

From a thousand to a million they are no more than ±3.1 % apart, less than the usual measurement noise. For the difference to grow to ±8 % one needs the range from a thousand to a billion, and even there an exponent can be found, 1.079, that is closer to n log n than 1.1. Six orders of magnitude of n can almost never be measured on one machine. The conclusion is unpleasant but honest: from seconds alone n log n cannot be told from n^1.08. The logarithm in the answer comes from knowing the algorithm; the measurement only confirms that nothing worse is hiding.

The ratio test

Take a candidate f and divide each time by f(n). If the candidate is right, the quotient is c with noise: it stays put. If the growth is faster than the candidate, the quotient grows; if slower, it falls. In the scene's table each candidate shows how its quotient goes from small n to large, and its spread is written down: the ratio of the largest value to the smallest over the upper half of the sizes.

Why the upper half? Because at small n the time is spoilt by fixed overheads: a function call, checks, memory allocation. In “Insert at the front” in Python they are visible directly: the work grows as n², but the slope on the first segments is about 1.8 and only approaches 2 at large n. The sum a·n + b·n² looks like a power only where the second term has crushed the first.

The spread also answers a specific question. The quotients fit into a corridor c·(1 ± r) for some c exactly when the spread is at most (1 + r)/(1 − r). A spread of 1.22 means “all measurements within ±10 % of one formula”, a spread of 1.5 “no better than ±20 %”. This is the problem at the end of the article.

Where measurement lies

Small n. Fixed overheads understate the exponent. Measure where one run lasts at least milliseconds, and draw conclusions from large n.

Memory. While the data fit in the processor's cache, each access is almost free; when they stop fitting, it gets several times dearer. On the graph this is a step: in “Sorting” in Go the slope jumps above 1.5 on one or two segments and then holds around 1.1 again; at these places the array stops fitting into the next level of cache. More about this wall is in the article “Cache-friendly data”.

Data. Complexity depends not only on the size of the input. “Sorting sorted data” grows linearly: Timsort in Python finds ready sorted runs, pdqsort in Go notices a ready order, and both go over the array once. A measurement on convenient data speaks about that data, not about the worst case.

It is worse when data are inconvenient unnoticeably. The first version of the multiplication measurement for this article showed a slope of 1.2 in Go and a time 19 times smaller than now at two million bits. The bytes of the numbers were taken from the low bits of a linear congruential generator, and the low 8 bits of such a generator modulo 2³² repeat every 256 steps. The numbers came out periodic, and their halves coincided. Karatsuba in Go computes the middle term as (x₀ − x₁)·(y₁ − y₀) + z₀ + z₂, and for such numbers the differences are almost zero: the third multiplication comes free, the recursion goes into two branches instead of three, and the growth drops almost to n log n. Python noticed nothing: in CPython the same term is computed through sums, (a_h + a_l)(b_h + b_l), and equal halves do not help it. The series “Multiplication: repeats” in the scene reproduces this mistake on purpose. None of the measurements looked suspicious; only the disagreement between the languages did.

Noise. Neighbouring processes, processor frequency, garbage collection. The cure is repetition and the minimum or median, which the article “How to benchmark honestly” is about. Noise affects the slope more than the time itself: it enters a difference of two logarithms.

Code

The first program does not measure but judges. Four “mysterious” sets of measurements with noise up to 8 %, n log n, n^1.585, a square with a noticeable linear part, and 2ⁿ, and for each: the slopes of the segments, the slope over the upper half and the ratio test. At the end, the twins from the second scene.

A: n from 1000 to 1024000
  local slopes: 1.05 1.17 1.04 1.26 0.89 1.12 1.22 1.07 1.03 1.04
  slope over the upper half: 1.10
  ratio test: n log n x1.12, n x1.40, n^1.585 x5.43
  verdict: n log n

The segment slopes in set A wander from 0.89 to 1.26, although the noise is only 8 %. The slope over the upper half is 1.10, and rounding would say “linear”. The ratio test tells them apart: for n log n the quotient is spread by 12 %, for n by 40 %. Over such a range, three orders of magnitude, this still works. Set C is a square plus a linear part: the slopes go from 1.3 to 2.1, and even over the upper half the spread of the quotient for n² is 1.45. This is a warning: a square with a large linear term looks like anything at small n.

The second program measures for real: it doubles n until one run takes 50 ms, repeats each size until 2 ms have accumulated, and takes the best of three measurements. Put your own function in place of the sort.

What a measurement costs

Doubling n comes cheap. Let the time grow as n^k, and let the last run last B. The previous one is 2^k times shorter, the one before it another 2^k, and all of them together cost at most

$$B\left(1 + 2^{-k} + 2^{-2k} + \dots\right) = B \cdot \frac{2^k}{2^k - 1}.$$

For linear growth that is 2B, for a square 4/3 B, for a cube 8/7 B. For an exponential, where n grows by one and the time is multiplied by b, the sum is B·b/(b − 1). So the whole measurement costs O(B): about as much as the longest run. Repeats multiply this by the number of attempts, and the threshold of 2 ms per size adds a few milliseconds for each small n. The ratio test itself is O(number of candidates × number of measurements): instant.

Where it is used

Olympiads and interviews. Before submitting a solution, it is run on n, 2n, 4n on random and on worst-case inputs. If the time grows fourfold each time and the limit is 10⁵, there is no need to wait for the verdict. How to turn steps into seconds is told in the article “How many operations per second”.

Finding places that grow wrongly. In 2007 Simon Goldsmith, Alex Aiken and Daniel Wilkerson described the tool trend-prof: it runs a program on inputs of different sizes, counts how many times each basic block of code executed, and fits power laws to these counts. A block whose exponent is larger than expected is a candidate for a performance bug, even if on the test inputs it costs nothing yet. Counts instead of seconds get rid of noise: the same idea as counting steps in the article on big O.

Hidden complexity of libraries. CPython for a long time converted a big integer to a decimal string in quadratic time. In 2022 this was recognised as a vulnerability, CVE-2020-10735: a long string of digits in a request kept a server's processor busy for a long time, and Python limited such conversions to 4300 digits by default. There was no square in any line of user code: it was in int() and str(). A measurement on several sizes finds such places before an attacker does.

History

The doubling test was made a habit by textbooks: in Sedgewick and Wayne's “Algorithms” the program DoublingRatio prints the time and the ratio of times when n doubles, and the reader guesses the exponent from the ratio, with the caveat that logarithmic factors cannot be seen this way. Fitting power laws to measurements grew into a field of its own, experimental algorithmics; a survey of it is Catherine McGeoch's book “A Guide to Experimental Algorithmics” (2012).

And the exponent 1.585 from the first scene comes from a story about growth itself. In 1960 Andrey Kolmogorov conjectured at a seminar that two n-digit numbers cannot be multiplied faster than in n². A week later the 23-year-old student Anatoly Karatsuba found a way to manage with three multiplications of halves instead of four: hence n^log₂3. Details are in the article on Karatsuba multiplication.

Problems

A table of measurements of someone else's program and eight candidates. Rounding the slope is useless: in the very first sample n log n pretends to be linear. The second sample is a real measurement of multiplication from this article.