Crate big_o 

big_o

Infers asymptotic computational complexity.

Measure how long your algorithm takes over a range of input sizes, hand the measurements to big_o, and it fits every complexity model it knows and reports the one that best describes them — along with how firmly the data supports that choice.

No dependencies.

Example

Real measurements, so a few percent of timing noise:

use big_o::Model;

let measurements = [
    (100., 10_180.),
    (200., 39_800.),
    (400., 161_440.),
    (800., 637_440.),
    (1600., 2_570_240.),
    (3200., 10_352_640.),
    (6400., 40_673_280.),
    (12800., 164_167_680.),
];

let inference = big_o::infer_complexity(&measurements).unwrap();

assert_eq!(inference.best.model, Model::Quadratic);
assert_eq!(inference.best.to_string(), "O(n^2)");

// Assert a bound rather than an exact match, the way you would in a test.
assert!(inference.best.is_at_most(Model::Quadratic));
assert!(inference.best.is_faster_than(Model::Cubic));

// How much of the answer is the data, and how much is the noise.
assert!(inference.confidence > 0.9);

Noise does not cost you the named answer: the measurements above are not exactly quadratic, and O(n^2) is still what you get rather than O(n^2.0004).

Reading the result

infer_complexity returns an Inference:

• best — the model that describes the data best, with its fitted coefficients, its r_squared, and its relative_error.
• all — every model that could be fitted, best first, if you want to see what came close.
• confidence — the fraction of resampled subsets of your measurements that chose the same model. Deterministic: the same input always gives the same number.
• warnings — conditions that weaken the result without invalidating it: too few input sizes, too narrow a range of them, cost that falls or that rises and falls, and models that could not be fitted at all.

A warning is worth reading before trusting a result. Complexity models are separated by how fast they grow, so what identifies them is the range of input sizes you measured, not the number of points in it — ten sizes between 1000 and 1100 look linear whatever produced them, and NarrowRange says so.

To weigh only the models you consider possible:

use big_o::{Analysis, Model};

let measurements = [(1., 1.), (2., 4.), (3., 9.), (4., 16.), (5., 25.)];

let inference = Analysis::new()
    .models([Model::Linear, Model::Quadratic])
    .infer(&measurements)
    .unwrap();

assert_eq!(inference.best.model, Model::Quadratic);

Accepting a short ladder

The range warnings advise the sample that makes every model separable. A real benchmark often cannot afford it — the widest rungs are the expensive ones — and a warning that fires on every run of an accepted trade-off stops being read. Declare the ladder you can afford, and the warnings fire only below it:

use big_o::Analysis;

let measurements = [(100., 105.), (200., 198.), (400., 405.), (1000., 1002.)];

let inference = Analysis::new()
    .accept_range(4, 1.0) // four sizes over one decade, knowingly
    .infer(&measurements)
    .unwrap();

assert!(inference.warnings.is_empty());

This changes which warnings are raised and nothing else — the inference is exactly as weak as it was; you have signed off on that weakness, not repaired it.

Serialization

The serde feature (off by default) derives Serialize/Deserialize for the result types, so an inference can be written down and compared against a later run — a committed baseline in CI, a saved report:

big_o = { version = "0.2", features = ["serde"] }

Inference is deterministic — the same measurements always produce the same result, including confidence — which is what makes a stored verdict worth comparing against at all. If you store as JSON and compare bit-exactly, enable serde_json’s float_roundtrip feature: its default float parsing can be an ulp off, which is drift a comparison would report as a change.

Errors

• NotEnoughData — fewer than three distinct input sizes. Repeated measurements of one size collapse to their median first, so they count once between them.
• NoValidComplexity — nothing among the candidate models describes the data.

Structs

Analysis

Inference with a restricted set of candidate models.

Fit

One model fitted to a set of measurements.

Inference

The outcome of inferring a complexity from measurements.

Enums

Error

Reasons a complexity could not be produced.

Model

A class of asymptotic computational complexity.

ModelParams

Coefficients of a fitted approximation function.

Warning

Something about the measurements that weakens the inference without invalidating it.

Functions

infer_complexity

Infers the asymptotic complexity of measured (input size, cost) pairs.