YES(?,O(n^2)) We are left with following problem, upon which TcT provides the certificate YES(?,O(n^2)). Strict Trs: { exp(x, 0()) -> s(0()) , exp(x, s(y)) -> *(x, exp(x, y)) , *(0(), y) -> 0() , *(s(x), y) -> +(y, *(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(exp) = {}, safe(0) = {}, safe(s) = {1}, safe(*) = {2}, safe(+) = {1, 2}, safe(-) = {1} and precedence exp > *, - > *, exp ~ - . Following symbols are considered recursive: {exp, *, -} The recursion depth is 2. For your convenience, here are the satisfied ordering constraints: exp(x, 0();) > s(; 0()) exp(x, s(; y);) > *(x; exp(x, y;)) *(0(); y) > 0() *(s(; x); y) > +(; y, *(x; y)) -(0(); x) > x -(y; 0()) > 0() -(s(; y); s(; x)) > -(y; x) Hurray, we answered YES(?,O(n^2))