YES(?,O(1)) We are left with following problem, upon which TcT provides the certificate YES(?,O(1)). Strict Trs: { first(0(), X) -> nil() , first(s(X), cons(Y)) -> cons(Y) , from(X) -> cons(X) } 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(first) = {1}, safe(0) = {}, safe(nil) = {}, safe(s) = {1}, safe(cons) = {1}, safe(from) = {} and precedence first > from . Following symbols are considered recursive: {} The recursion depth is 0. For your convenience, here are the satisfied ordering constraints: first(X; 0()) > nil() first(cons(; Y); s(; X)) > cons(; Y) from(X;) > cons(; X) Hurray, we answered YES(?,O(1))