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