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 {araHeuristics = NoHeuristics, minDegree = 1, maxDegree = 2, araTimeout = 5, araRuleShifting = Nothing} + Details: Signatures used: ---------------- 0 :: [] -(0)-> "A"(14) 0 :: [] -(0)-> "A"(5) 0 :: [] -(0)-> "A"(0) 0 :: [] -(0)-> "A"(13) app :: ["A"(0) x "A"(1)] -(0)-> "A"(1) div :: ["A"(5) x "A"(0)] -(4)-> "A"(1) div' :: ["A"(14) x "A"(14)] -(0)-> "A"(14) div' :: ["A"(0) x "A"(0)] -(0)-> "A"(0) div' :: ["A"(15) x "A"(15)] -(0)-> "A"(15) egypt :: ["A"(14)] -(3)-> "A"(1) h :: ["A"(5) x "A"(0) x "A"(0)] -(3)-> "A"(1) i :: ["A"(0) x "A"(0)] -(1)-> "A"(15) minus :: ["A"(0) x "A"(0)] -(0)-> "A"(15) mult :: ["A"(0) x "A"(0)] -(0)-> "A"(10) mult :: ["A"(0) x "A"(0)] -(0)-> "A"(11) mult :: ["A"(0) x "A"(0)] -(0)-> "A"(15) nil :: [] -(0)-> "A"(7) s :: ["A"(14)] -(14)-> "A"(14) s :: ["A"(5)] -(5)-> "A"(5) s :: ["A"(0)] -(0)-> "A"(0) s :: ["A"(1)] -(1)-> "A"(1) s :: ["A"(3)] -(3)-> "A"(3) Cost-free Signatures used: -------------------------- Base Constructor Signatures used: --------------------------------- "0_A" :: [] -(0)-> "A"(1) "app_A" :: ["A"(0) x "A"(1)] -(0)-> "A"(1) "div'_A" :: ["A"(0) x "A"(0)] -(0)-> "A"(0) "minus_A" :: ["A"(0) x "A"(0)] -(0)-> "A"(1) "mult_A" :: ["A"(0) x "A"(0)] -(0)-> "A"(1) "nil_A" :: [] -(0)-> "A"(1) "s_A" :: ["A"(1)] -(1)-> "A"(1) WORST_CASE(?,O(n^1))