YES(?,O(n^2)) We are left with following problem, upon which TcT provides the certificate YES(?,O(n^2)). Strict Trs: { +(0(), y) -> y , +(s(x), y) -> s(+(x, y)) , -(x, 0()) -> x , -(0(), y) -> 0() , -(s(x), s(y)) -> -(x, y) } Obligation: innermost runtime complexity Answer: YES(?,O(n^2)) The input was oriented with the instance of 'Small Polynomial Path Order (PS)' as induced by the safe mapping safe(+) = {}, safe(0) = {}, safe(s) = {1}, safe(-) = {1} and precedence + > - . Following symbols are considered recursive: {+, -} The recursion depth is 2. For your convenience, here are the satisfied ordering constraints: +(0(), y;) > y +(s(; x), y;) > s(; +(x, y;)) -(0(); x) > x -(y; 0()) > 0() -(s(; y); s(; x)) > -(y; x) Hurray, we answered YES(?,O(n^2))