Determine time complexity of the function:

>>> fit $ mkFitConfig (\x -> sum [1..x]) (10, 10000)
1.2153e-8 * x
>>> fit $ mkFitConfig (\x -> Data.List.nub [1..x]) (10, 10000)
2.8369e-9 * x ^ 2
>>> fit $ mkFitConfig (\x -> Data.List.sort $ take (fromIntegral x) $ iterate (\n -> n * 6364136223846793005 + 1) (1 :: Int)) (10, 100000)
5.2990e-8 * x * log x

One can usually get reliable results for functions, which do not allocate much: like in-place vector sort or fused list operations like sum [1..x].

Unfortunately, fitting functions, which allocate a lot, is likely to be disappointing: GC kicks in irregularly depending on nursery and heap sizes and often skews observations beyond any recognition. Consider running such measurements with -O0 or in ghci prompt. This is how the usage example above was generated. Without optimizations your program allocates much more and triggers GC regularly, somewhat evening out its effect.

Same as fit, but interactively emits a list of complexities, gradually converging to the final result.

If fit takes too long, you might wish to implement your own criterion of convergence atop of fits directly.

Generate a default fit configuration.

Configuration for fit.

Complexity a b k represents a time complexity \( k \, x^a \log^b x \), where \( x \) is problem's size.

Represents a time measurement for a given problem's size.

Guess time complexity from a map where keys are problem's sizes and values are time measurements (or instruction counts).

>>> :set -XNumDecimals
>>> guessComplexity $ Data.Map.fromList $ map (\(x, t) -> (x, Measurement t 1)) [(2, 4), (3, 10), (4, 15), (5, 25)]
0.993 * x ^ 2
>>> guessComplexity $ Data.Map.fromList $ map (\(x, t) -> (x, Measurement t 1)) [(1e2, 2.1), (1e3, 2.9), (1e4, 4.1), (1e5, 4.9)]
0.433 * log x

This function uses following simplifying assumptions:

• All coefficients are non-negative.
• The power of \( \log x \) (cmplLogPower) is unlikely to be \( > 1 \).
• The power of \( x \) (cmplVarPower) is unlikely to be fractional.

This function is unsuitable to guess superpolynomial and higher classes of complexity.

Evaluate time complexity for a given size of the problem.

Is the complexity \( f(x) = k \)?

Is the complexity \( f(x) = k \log x \)?

Is the complexity \( f(x) = k \, x \)?

Is the complexity \( f(x) = k \, x \log x \)?

Is the complexity \( f(x) = k \, x^2 \)?

Is the complexity \( f(x) = k \, x^3 \)?