problemreductions/
big_o.rs

1//! Big-O asymptotic normal form.
2//!
3//! Thin wrapper over the [growth domain](crate::growth): compute the growth
4//! class of an expression bottom-up (without fully distributing the source AST) and
5//! render it back to a display [`Expr`]. Content the growth domain cannot bound
6//! symbolically (nonlinear exponents, factorials, negative exponents) maps to
7//! the [`AsymptoticAnalysisError::Unsupported`] error.
8
9use crate::expr::{AsymptoticAnalysisError, Expr};
10use crate::growth::Growth;
11
12/// Compute the Big-O normal form of an expression.
13///
14/// Returns an expression representing the asymptotic growth class, or
15/// [`AsymptoticAnalysisError::Unsupported`] when the growth domain cannot
16/// represent the input.
17pub fn big_o_normal_form(expr: &Expr) -> Result<Expr, AsymptoticAnalysisError> {
18    let growth = Growth::from_expr(expr);
19    match growth.to_expr() {
20        Some(expression) => Ok(expression),
21        None => Err(AsymptoticAnalysisError::Unsupported(
22            growth
23                .failures()
24                .expect("growth without an expression must contain failure reasons")
25                .iter()
26                .map(ToString::to_string)
27                .collect::<Vec<_>>()
28                .join("; "),
29        )),
30    }
31}
32
33#[cfg(test)]
34#[path = "unit_tests/big_o.rs"]
35mod tests;
problemreductions/big_o.rs

problemreductions/
big_o.rs
