YES(O(1),O(n^3)) We are left with following problem, upon which TcT provides the certificate YES(O(1),O(n^3)). Strict Trs: { p(s(x)) -> x , fac(s(x)) -> times(s(x), fac(p(s(x)))) , fac(0()) -> s(0()) } Obligation: innermost runtime complexity Answer: YES(O(1),O(n^3)) We add following weak dependency pairs: Strict DPs: { p^#(s(x)) -> c_1() , fac^#(s(x)) -> c_2(fac^#(p(s(x)))) , fac^#(0()) -> c_3() } and mark the set of starting terms. We are left with following problem, upon which TcT provides the certificate YES(O(1),O(n^3)). Strict DPs: { p^#(s(x)) -> c_1() , fac^#(s(x)) -> c_2(fac^#(p(s(x)))) , fac^#(0()) -> c_3() } Strict Trs: { p(s(x)) -> x , fac(s(x)) -> times(s(x), fac(p(s(x)))) , fac(0()) -> s(0()) } Obligation: innermost runtime complexity Answer: YES(O(1),O(n^3)) We replace rewrite rules by usable rules: Strict Usable Rules: { p(s(x)) -> x } We are left with following problem, upon which TcT provides the certificate YES(O(1),O(n^3)). Strict DPs: { p^#(s(x)) -> c_1() , fac^#(s(x)) -> c_2(fac^#(p(s(x)))) , fac^#(0()) -> c_3() } Strict Trs: { p(s(x)) -> x } Obligation: innermost runtime complexity Answer: YES(O(1),O(n^3)) The weightgap principle applies (using the following constant growth matrix-interpretation) The following argument positions are usable: Uargs(fac^#) = {1}, Uargs(c_2) = {1} TcT has computed following constructor-restricted matrix interpretation. [p](x1) = [1] x1 + [0] [s](x1) = [1] x1 + [2] [0] = [1] [p^#](x1) = [1] x1 + [1] [c_1] = [1] [fac^#](x1) = [2] x1 + [2] [c_2](x1) = [1] x1 + [1] [c_3] = [1] This order satisfies following ordering constraints: [p(s(x))] = [1] x + [2] > [1] x + [0] = [x] Further, it can be verified that all rules not oriented are covered by the weightgap condition. We are left with following problem, upon which TcT provides the certificate YES(?,O(n^3)). Strict DPs: { fac^#(s(x)) -> c_2(fac^#(p(s(x)))) } Weak DPs: { p^#(s(x)) -> c_1() , fac^#(0()) -> c_3() } Weak Trs: { p(s(x)) -> x } Obligation: innermost runtime complexity Answer: YES(?,O(n^3)) The following weak DPs constitute a sub-graph of the DG that is closed under successors. The DPs are removed. { p^#(s(x)) -> c_1() , fac^#(0()) -> c_3() } We are left with following problem, upon which TcT provides the certificate YES(?,O(n^3)). Strict DPs: { fac^#(s(x)) -> c_2(fac^#(p(s(x)))) } Weak Trs: { p(s(x)) -> x } Obligation: innermost runtime complexity Answer: YES(?,O(n^3)) The following argument positions are usable: Uargs(c_2) = {1} TcT has computed following constructor-based matrix interpretation satisfying not(EDA). [1 0 0] [0] [p](x1) = [0 0 1] x1 + [0] [1 0 0] [0] [1 0 1] [0] [s](x1) = [0 1 0] x1 + [1] [0 1 0] [0] [0 1 0] [0] [fac^#](x1) = [0 0 0] x1 + [0] [0 0 0] [0] [1 0 0] [0] [c_2](x1) = [0 0 0] x1 + [0] [0 0 0] [0] This order satisfies following ordering constraints: [p(s(x))] = [1 0 1] [0] [0 1 0] x + [0] [1 0 1] [0] >= [1 0 0] [0] [0 1 0] x + [0] [0 0 1] [0] = [x] [fac^#(s(x))] = [0 1 0] [1] [0 0 0] x + [0] [0 0 0] [0] > [0 1 0] [0] [0 0 0] x + [0] [0 0 0] [0] = [c_2(fac^#(p(s(x))))] Hurray, we answered YES(O(1),O(n^3))