WORST_CASE(?,O(n^2)) * Step 1: NaturalPI WORST_CASE(?,O(n^2)) + Considered Problem: - Strict TRS: if_mod(false(),s(x),s(y)) -> s(x) if_mod(true(),s(x),s(y)) -> mod(minus(x,y),s(y)) le(0(),y) -> true() le(s(x),0()) -> false() le(s(x),s(y)) -> le(x,y) minus(x,0()) -> x minus(s(x),s(y)) -> minus(x,y) mod(0(),y) -> 0() mod(s(x),0()) -> 0() mod(s(x),s(y)) -> if_mod(le(y,x),s(x),s(y)) - Signature: {if_mod/3,le/2,minus/2,mod/2} / {0/0,false/0,s/1,true/0} - Obligation: innermost runtime complexity wrt. defined symbols {if_mod,le,minus,mod} and constructors {0,false,s,true} + Applied Processor: NaturalPI {shape = Quadratic, restrict = NoRestrict, uargs = UArgs, urules = URules, selector = Nothing} + Details: We apply a polynomial interpretation of kind constructor-based(quadratic): The following argument positions are considered usable: uargs(if_mod) = {1}, uargs(mod) = {1} Following symbols are considered usable: {if_mod,le,minus,mod} TcT has computed the following interpretation: p(0) = 0 p(false) = 1 p(if_mod) = 2*x1 + 3*x2 + x2^2 p(le) = 2 + x2 p(minus) = 1 + x1 p(mod) = 1 + 5*x1 + x1^2 p(s) = 2 + x1 p(true) = 0 Following rules are strictly oriented: if_mod(false(),s(x),s(y)) = 12 + 7*x + x^2 > 2 + x = s(x) if_mod(true(),s(x),s(y)) = 10 + 7*x + x^2 > 7 + 7*x + x^2 = mod(minus(x,y),s(y)) le(0(),y) = 2 + y > 0 = true() le(s(x),0()) = 2 > 1 = false() le(s(x),s(y)) = 4 + y > 2 + y = le(x,y) minus(x,0()) = 1 + x > x = x minus(s(x),s(y)) = 3 + x > 1 + x = minus(x,y) mod(0(),y) = 1 > 0 = 0() mod(s(x),0()) = 15 + 9*x + x^2 > 0 = 0() mod(s(x),s(y)) = 15 + 9*x + x^2 > 14 + 9*x + x^2 = if_mod(le(y,x),s(x),s(y)) Following rules are (at-least) weakly oriented: WORST_CASE(?,O(n^2))