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