pberkes / big_O

Python module to estimate big-O time complexity from execution time
BSD 3-Clause "New" or "Revised" License
323 stars 50 forks source link

Floating-point precision when interpreting exponential dependence #62

Open yavnolib opened 1 month ago

yavnolib commented 1 month ago

When calculating the complexity, I got the following results:

Best : Exponential: time = 0.036 * 1^n (sec)
Constant: time = 0.5 (sec) (res: 5.5)
Linear: time = -0.43 + 0.0065*n (sec) (res: 1.7)
Quadratic: time = -0.098 + 2.4E-05*n^2 (sec) (res: 1)
Cubic: time = 0.024 + 9.6E-08*n^3 (sec) (res: 0.69)
Polynomial: time = 9.9E-05 * x^1.7 (sec) (res: 1.8)
Logarithmic: time = -2.6 + 0.64*log(n) (sec) (res: 2.7)
Linearithmic: time = -0.31 + 0.0011*n*log(n) (sec) (res: 1.5) 
Exponential: time = 0.036 * 1^n (sec) (res: 0.6)

It seems to me that in the exponential dependence the value of the coefficient b should be shown in full, or the number of digits after the decimal point should be increased, since the exponent grows too quickly. The actual value of the coefficient b in this case is 1.01498.

pberkes commented 1 month ago

The formatting string is 'time = {:.2G} * {:.2G}^n', so yes in this case 1.01498 would be printed as 1.

We could increase .2 to .3, but the G format often does automatically the right thing... but would one do that for all the cases? I'm wondering if we should have a global display option instead, for the precision of these reports