WORST_CASE(?,O(1)) proof of /export/starexec/sandbox2/benchmark/theBenchmark.trs # AProVE Commit ID: c69e44bd14796315568835c1ffa2502984884775 mhark 20210624 unpublished The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(1, 1). (0) CpxTRS (1) NarrowingOnBasicTermsTerminatesProof [FINISHED, 0 ms] (2) BOUNDS(1, 1) ---------------------------------------- (0) Obligation: The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(1, 1). The TRS R consists of the following rules: f(g(i(a, b, b'), c), d) -> if(e, f(.(b, c), d'), f(.(b', c), d')) f(g(h(a, b), c), d) -> if(e, f(.(b, g(h(a, b), c)), d), f(c, d')) S is empty. Rewrite Strategy: INNERMOST ---------------------------------------- (1) NarrowingOnBasicTermsTerminatesProof (FINISHED) Constant runtime complexity proven by termination of constructor-based narrowing. The maximal most general narrowing sequences give rise to the following rewrite sequences: f(g(h(a, b), c), d) ->^* if(e, f(.(b, g(h(a, b), c)), d), f(c, d')) f(g(i(a, b, b'), c), d) ->^* if(e, f(.(b, c), d'), f(.(b', c), d')) ---------------------------------------- (2) BOUNDS(1, 1)