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