WORST_CASE(?,O(n^1)) * Step 1: Ara WORST_CASE(?,O(n^1)) + Considered Problem: - Strict TRS: div(x,y) -> h(x,y,y) egypt(div'(0(),y)) -> nil() egypt(div'(s(x),y)) -> app(div(y,s(x)),egypt(i(div'(s(x),y),div'(s(0()),div(y,s(x)))))) h(s(0()),y,z) -> s(0()) h(s(s(x)),s(0()),z) -> s(h(s(x),z,z)) h(s(s(x)),s(s(y)),z) -> h(s(x),s(y),z) i(div'(x,y),div'(u,v)) -> div'(minus(mult(x,v),mult(y,u)),mult(y,v)) - Signature: {div/2,egypt/1,h/3,i/2} / {0/0,app/2,div'/2,minus/2,mult/2,nil/0,s/1} - Obligation: innermost runtime complexity wrt. defined symbols {div,egypt,h,i} and constructors {0,app,div',minus,mult ,nil,s} + Applied Processor: Ara {minDegree = 1, maxDegree = 2, araTimeout = 5, araRuleShifting = Nothing} + Details: Signatures used: ---------------- F (TrsFun "0") :: [] -(0)-> "A"(10) F (TrsFun "0") :: [] -(0)-> "A"(4) F (TrsFun "0") :: [] -(0)-> "A"(0) F (TrsFun "0") :: [] -(0)-> "A"(15) F (TrsFun "app") :: ["A"(0) x "A"(0)] -(0)-> "A"(12) F (TrsFun "div") :: ["A"(4) x "A"(0)] -(1)-> "A"(0) F (TrsFun "div'") :: ["A"(10) x "A"(10)] -(0)-> "A"(10) F (TrsFun "div'") :: ["A"(1) x "A"(1)] -(0)-> "A"(1) F (TrsFun "div'") :: ["A"(0) x "A"(0)] -(0)-> "A"(0) F (TrsFun "div'") :: ["A"(15) x "A"(15)] -(0)-> "A"(15) F (TrsFun "egypt") :: ["A"(10)] -(6)-> "A"(8) F (TrsFun "h") :: ["A"(4) x "A"(0) x "A"(0)] -(0)-> "A"(0) F (TrsFun "i") :: ["A"(1) x "A"(0)] -(1)-> "A"(15) F (TrsFun "minus") :: ["A"(0) x "A"(0)] -(0)-> "A"(15) F (TrsFun "mult") :: ["A"(0) x "A"(0)] -(0)-> "A"(11) F (TrsFun "mult") :: ["A"(0) x "A"(0)] -(0)-> "A"(15) F (TrsFun "nil") :: [] -(0)-> "A"(15) F (TrsFun "s") :: ["A"(10)] -(10)-> "A"(10) F (TrsFun "s") :: ["A"(4)] -(4)-> "A"(4) F (TrsFun "s") :: ["A"(0)] -(0)-> "A"(0) F (TrsFun "s") :: ["A"(1)] -(1)-> "A"(1) Cost-free Signatures used: -------------------------- Base Constructor Signatures used: --------------------------------- "F (TrsFun \"0\")_A" :: [] -(0)-> "A"(1) "F (TrsFun \"app\")_A" :: ["A"(0) x "A"(0)] -(0)-> "A"(1) "F (TrsFun \"div'\")_A" :: ["A"(1) x "A"(1)] -(0)-> "A"(1) "F (TrsFun \"minus\")_A" :: ["A"(0) x "A"(0)] -(0)-> "A"(1) "F (TrsFun \"mult\")_A" :: ["A"(0) x "A"(0)] -(0)-> "A"(1) "F (TrsFun \"nil\")_A" :: [] -(0)-> "A"(1) "F (TrsFun \"s\")_A" :: ["A"(1)] -(1)-> "A"(1) WORST_CASE(?,O(n^1))