YES(?,O(n^2)) We are left with following problem, upon which TcT provides the certificate YES(?,O(n^2)). Strict Trs: { a__c() -> a__f(g(c())) , a__c() -> c() , a__f(X) -> f(X) , a__f(g(X)) -> g(X) , mark(g(X)) -> g(X) , mark(c()) -> a__c() , mark(f(X)) -> a__f(X) } 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(a__c) = {}, safe(a__f) = {1}, safe(g) = {1}, safe(c) = {}, safe(mark) = {1}, safe(f) = {1} and precedence a__c > a__f, mark > a__c, mark > a__f . Following symbols are considered recursive: {a__f, mark} The recursion depth is 2. For your convenience, here are the satisfied ordering constraints: a__c() > a__f(; g(; c())) a__c() > c() a__f(; X) > f(; X) a__f(; g(; X)) > g(; X) mark(; g(; X)) > g(; X) mark(; c()) > a__c() mark(; f(; X)) > a__f(; X) Hurray, we answered YES(?,O(n^2))