Enum ComplexityClass 

pub enum ComplexityClass {
    Logarithmic,
    PolyLogarithmic,
    SubLinear,
    Linear,
    QuasiLinear,
    SubQuadratic,
    Polynomial(u8),
    SuperPolynomial,
    SubExponential,
    Exponential,
    Factorial,
    DoubleExponential,
    Adaptive {
        default: &'static ComplexityClass,
        worst: &'static ComplexityClass,
    },
}

The twelve-tier complexity taxonomy from the directive in ADR-001.

Ordering is by asymptotic growth: Logarithmic is “easiest” / “cheapest”, DoubleExponential is “hardest” / “most expensive”. PartialOrd / Ord lift this into a usable budget comparison — c <= max_budget means c is at most as expensive as the budget, so a caller with a SubLinear budget will accept Logarithmic and PolyLogarithmic and reject anything stronger.

The single-parameter Polynomial(degree) is ranked by its degree; Polynomial(2) precedes Polynomial(3) etc. Adaptive solvers that degrade on hard inputs can use Adaptive { default, worst } so the caller sees both bounds.

Variants

Logarithmic

O(log n) — binary search, HNSW layer traversal, sublinear-Neumann single-entry query on a DD system.

PolyLogarithmic

O((log n)^k) — spectral sparsifiers, dynamic connectivity, live graph repair. The “polylog” tier.

SubLinear

O(n^c), c < 1 — approximate nearest neighbour, sparse attention, event-driven activation, anomaly detection.

Linear

O(n) — one-pass streaming, ingest, WAL replay, sensor scan.

QuasiLinear

O(n log n) — sorting, indexing, ANN build, graph compression. The “practical sweet spot” for offline preprocessing.

SubQuadratic

O(n^{2-ε}) — sparsified mincut, sub-quadratic graph algorithms.

Polynomial(u8)

O(n^k) — classical polynomial algorithms (matrix multiply for k=3, dense linear solves for k=2.37+, etc.). Degree of the polynomial is carried so callers can prefer lower-degree solvers.

SuperPolynomial

Worse than any fixed polynomial but better than exponential. Combinatorial enumeration with strong pruning lives here.

SubExponential

2^{O(n^c)}, c < 1 — SAT solvers, advanced cryptography, optimisation.

Exponential

O(2^n) — brute-force search, exhaustive planning, unrestricted combinatorics. Catastrophic at any non-trivial scale.

Factorial

O(n!) — permutation search, exhaustive TSP. “Heat death of the universe territory” at n ≥ 20.

DoubleExponential

O(2^{2^n}) — formal systems, symbolic explosion. Theoretical only.

Adaptive

Adaptive — a solver that runs at default on typical inputs but can degrade to worst on adversarial inputs. Callers should budget against worst to be safe.

Fields

default: &'static ComplexityClass

worst: &'static ComplexityClass

Implementations

impl ComplexityClass

pub const fn rank(&self) -> u16

Rank suitable for ordering. Lower = cheaper. Adaptive ranks by its worst bound so callers comparing against a budget see the safe upper bound.

pub const fn short_label(&self) -> &'static str

Short human-readable label suitable for log lines and MCP tool schemas.

pub const fn is_edge_safe(&self) -> bool

True if this class is acceptable for a real-time / edge / always-on hot path. Currently: anything strictly cheaper than Linear. Linear itself is conditional (acceptable for one-pass streaming, not for per-query work) — callers needing nuance should match directly.

Trait Implementations

impl Clone for ComplexityClass

fn clone(&self) -> ComplexityClass

Returns a duplicate of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl Debug for ComplexityClass

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl Hash for ComplexityClass

fn hash<__H: Hasher>(&self, state: &mut __H)

Feeds this value into the given Hasher.

fn hash_slice<H>(data: &[Self], state: &mut H)

where H: Hasher, Self: Sized,

Feeds a slice of this type into the given Hasher.

impl Ord for ComplexityClass

fn cmp(&self, other: &Self) -> Ordering

This method returns an Ordering between self and other.

fn max(self, other: Self) -> Self

where Self: Sized,

Compares and returns the maximum of two values.

fn min(self, other: Self) -> Self

where Self: Sized,

Compares and returns the minimum of two values.

fn clamp(self, min: Self, max: Self) -> Self

where Self: Sized,

Restrict a value to a certain interval.

impl PartialEq for ComplexityClass

fn eq(&self, other: &ComplexityClass) -> bool

Tests for self and other values to be equal, and is used by ==.

fn ne(&self, other: &Rhs) -> bool

Tests for !=. The default implementation is almost always sufficient, and should not be overridden without very good reason.

impl PartialOrd for ComplexityClass

fn partial_cmp(&self, other: &Self) -> Option<Ordering>

This method returns an ordering between self and other values if one exists.

fn lt(&self, other: &Rhs) -> bool

Tests less than (for self and other) and is used by the < operator.

fn le(&self, other: &Rhs) -> bool

Tests less than or equal to (for self and other) and is used by the <= operator.

fn gt(&self, other: &Rhs) -> bool

Tests greater than (for self and other) and is used by the > operator.

fn ge(&self, other: &Rhs) -> bool

Tests greater than or equal to (for self and other) and is used by the >= operator.

impl Copy for ComplexityClass

impl Eq for ComplexityClass

impl StructuralPartialEq for ComplexityClass