CS
Problems Base course RU

Problem

A verdict from measurements

measurement estimation numerical precision

A colleague ran someone else's program on inputs of different sizes and sent a table: the input size n and the running time. There is no source, and an answer is needed today: how does its time grow? Choose one of eight models:

1, log n, n, n log n, n^1.585, n^2, n^3, 2^n.

The measurements are noisy, but not too noisy. For the right model f there is a number c > 0 such that each time differs from c·f(n) by at most 10 %: 0.9·c·f(n) ≤ t ≤ 1.1·c·f(n). And for any other model g there is no c for which all the times at once differ from c·g(n) by less than 20 %. So the answer is always unique.

The second sample is a real measurement: Python multiplies two random numbers of n bits, the best of nine runs.

Input

The first line holds the number of measurements m (3 ≤ m ≤ 40). Then m lines: an integer n (2 ≤ n ≤ 109) and a time t, a positive number at most 1012, in ordinary or exponential notation (0.00617, 4.07876e-05). The sizes are increasing and do not repeat.

Output

The model exactly as written above, for example n log n.

Examples

Example 1

Input
10
1000 0.197877
2000 0.44526
4000 0.962032
8000 2.33301
16000 4.5603
32000 10.1556
64000 20.8713
128000 43.8851
256000 100.572
512000 209.795
Output
n log n

Example 2

Input
8
4096 0.00617
8192 0.01972
16384 0.05788
32768 0.17655
65536 0.52948
131072 1.65769
262144 5.11409
524288 14.7766
Output
n^1.585

Limits

Time · Python
2000 ms
Time · Go
1000 ms
Memory
256 MB
Judging
12 tests

Walkthrough

Open it step by step: each step gives away a little more. You can jump straight to the solution, but a problem solved with one hint stays with you longer.

1Hint 1

The slope on logarithmic axes is the first thing that comes to mind. Compute it for the first sample. Which model does it suggest, and why is that not the answer?

2Hint 2

If a model is right, t/f(n) hardly changes: it is c with noise. From a set of numbers t/f(n), how do you tell whether there is one c from which all of them differ by at most 20 %?

3The idea

Divide the time by each model and look at the spread: the ratio of the largest quotient t/f(n) to the smallest. All the quotients fit into a corridor c·(1 ± r) for some c exactly when the spread is at most (1 + r)/(1 − r). For the right model the spread is at most 1.1/0.9 ≈ 1.22, for any other at least 1.2/0.8 = 1.5. So the answer is the model with the smallest spread.

4Walkthrough

Why the corridor and the spread are the same thing. Let the quotients lie between qmin and qmax. The corridor [c(1 − r), c(1 + r)] covers them if c(1 − r) ≤ qmin and c(1 + r) ≥ qmax, that is, qmax/(1 + r) ≤ c ≤ qmin/(1 − r). Such a c exists if the left bound is no greater than the right: qmax/qmin ≤ (1 + r)/(1 − r). The factor c itself need not be found.

It is more convenient to compute in logarithms: ln t − ln f(n), with the spread as the difference of the largest and smallest. Division becomes subtraction, and 2n at n = 109 does not overflow: ln 2n = n ln 2. The base of the logarithm in the models log n and n log n does not matter: it changes all quotients by the same factor, and the spread stays the same.

In the first sample the slope over all points is about 1.1, and rounding gives “n”. But the quotients t/n double from the first measurement to the last, while t/(n log n) stay put up to noise. The local slope of n log n is 1 + 1/ln n, and at such n it is about 1.1: the logarithmic factor hides in tenths of the slope. In the second sample the slope holds around 1.6, and this is not noise but log2 3 ≈ 1.585: Python multiplies big numbers by Karatsuba's algorithm. The ratio test, the twins n log n and n1.1 and where measurements lie are covered in detail in the article “Complexity from measurements”.

Here the quotients are taken over all measurements, because the noise is bounded by the statement. On real measurements this is not advisable: at small n the time is spoilt by fixed overheads, a start-up, a call, memory allocation, and the ratio test is done over the upper half of the sizes.

4+Solution
5Complexity

O(8·m): one pass over the measurements per model.

6Common mistakes
  • Rounding the slope. n log n turns into n, and log n into 1: the first sample, the fourth and eighth tests.
  • The slope over the last two points. One segment is two measurements, and the noise of both goes entirely into the answer: with 10 % per measurement the slope of the segment between n and 2n may be off by ±0.3.
  • Computing 2n as a number. With n up to 109 this overflows, and the quotient t/2n turns to zero. Logarithms are needed.
  • Choosing c from the first measurement. If you take c = t1/f(n1) and check the deviation of the others, the noise of the first measurement falls on all of them: the right model may “fail” the 10 %. Look at the spread of the quotients: it does not depend on the choice of c.

Algorithms behind it

TEC Technique Complexity from measurements The growth of running time from measurements: the slope, the ratio test, exponentials, and where measurement lies. O(B) per attempt 1 problem TEC Technique Big O How work grows with the data: O, Ω and Θ, rules for estimating code, and where asymptotics mislead. estimated from the program text 1 problem
The algorithms catalogue