WORST_CASE(?,O(n^1)) * Step 1: Ara WORST_CASE(?,O(n^1)) + Considered Problem: - Strict TRS: group3(@l) -> group3#1(@l) group3#1(::(@x,@xs)) -> group3#2(@xs,@x) group3#1(nil()) -> nil() group3#2(::(@y,@ys),@x) -> group3#3(@ys,@x,@y) group3#2(nil(),@x) -> nil() group3#3(::(@z,@zs),@x,@y) -> ::(tuple#3(@x,@y,@z),group3(@zs)) group3#3(nil(),@x,@y) -> nil() zip3(@l1,@l2,@l3) -> zip3#1(@l1,@l2,@l3) zip3#1(::(@x,@xs),@l2,@l3) -> zip3#2(@l2,@l3,@x,@xs) zip3#1(nil(),@l2,@l3) -> nil() zip3#2(::(@y,@ys),@l3,@x,@xs) -> zip3#3(@l3,@x,@xs,@y,@ys) zip3#2(nil(),@l3,@x,@xs) -> nil() zip3#3(::(@z,@zs),@x,@xs,@y,@ys) -> ::(tuple#3(@x,@y,@z),zip3(@xs,@ys,@zs)) zip3#3(nil(),@x,@xs,@y,@ys) -> nil() - Signature: {group3/1,group3#1/1,group3#2/2,group3#3/3,zip3/3,zip3#1/3,zip3#2/4,zip3#3/5} / {::/2,nil/0,tuple#3/3} - Obligation: innermost runtime complexity wrt. defined symbols {group3,group3#1,group3#2,group3#3,zip3,zip3#1,zip3#2 ,zip3#3} and constructors {::,nil,tuple#3} + Applied Processor: Ara {heuristics_ = NoHeuristics, minDegree = 1, maxDegree = 3, araTimeout = 60, araFindStrictRules = Nothing, araSmtSolver = Z3} + Details: Signatures used: ---------------- :: :: [A(13) x A(13)] -(13)-> A(13) :: :: [A(4) x A(4)] -(4)-> A(4) :: :: [A(10) x A(10)] -(10)-> A(10) :: :: [A(15) x A(15)] -(15)-> A(15) :: :: [A(3) x A(3)] -(3)-> A(3) :: :: [A(2) x A(2)] -(2)-> A(2) group3 :: [A(13)] -(11)-> A(3) group3#1 :: [A(13)] -(7)-> A(3) group3#2 :: [A(13) x A(13)] -(1)-> A(3) group3#3 :: [A(13) x A(13) x A(13)] -(10)-> A(3) nil :: [] -(0)-> A(13) nil :: [] -(0)-> A(4) nil :: [] -(0)-> A(10) nil :: [] -(0)-> A(15) nil :: [] -(0)-> A(5) tuple#3 :: [A(9) x A(9) x A(9)] -(0)-> A(9) tuple#3 :: [A(2) x A(2) x A(2)] -(0)-> A(2) zip3 :: [A(4) x A(10) x A(15)] -(9)-> A(2) zip3#1 :: [A(4) x A(10) x A(15)] -(7)-> A(2) zip3#2 :: [A(10) x A(15) x A(4) x A(4)] -(2)-> A(2) zip3#3 :: [A(15) x A(4) x A(4) x A(10) x A(10)] -(8)-> A(2) Cost-free Signatures used: -------------------------- :: :: [A_cf(0) x A_cf(0)] -(0)-> A_cf(0) group3 :: [A_cf(0)] -(0)-> A_cf(0) group3#1 :: [A_cf(0)] -(0)-> A_cf(0) group3#2 :: [A_cf(0) x A_cf(0)] -(0)-> A_cf(0) group3#3 :: [A_cf(0) x A_cf(0) x A_cf(0)] -(0)-> A_cf(0) nil :: [] -(0)-> A_cf(0) tuple#3 :: [A_cf(0) x A_cf(0) x A_cf(0)] -(0)-> A_cf(0) zip3 :: [A_cf(0) x A_cf(0) x A_cf(0)] -(0)-> A_cf(0) zip3#1 :: [A_cf(0) x A_cf(0) x A_cf(0)] -(0)-> A_cf(0) zip3#2 :: [A_cf(0) x A_cf(0) x A_cf(0) x A_cf(0)] -(0)-> A_cf(0) zip3#3 :: [A_cf(0) x A_cf(0) x A_cf(0) x A_cf(0) x A_cf(0)] -(0)-> A_cf(0) Base Constructor Signatures used: --------------------------------- ::_A :: [A(0) x A(0)] -(0)-> A(0) nil_A :: [] -(0)-> A(1) tuple#3_A :: [A(0) x A(0) x A(0)] -(0)-> A(0) * Step 2: Open MAYBE - Strict TRS: group3(@l) -> group3#1(@l) group3#1(::(@x,@xs)) -> group3#2(@xs,@x) group3#1(nil()) -> nil() group3#2(::(@y,@ys),@x) -> group3#3(@ys,@x,@y) group3#2(nil(),@x) -> nil() group3#3(::(@z,@zs),@x,@y) -> ::(tuple#3(@x,@y,@z),group3(@zs)) group3#3(nil(),@x,@y) -> nil() zip3(@l1,@l2,@l3) -> zip3#1(@l1,@l2,@l3) zip3#1(::(@x,@xs),@l2,@l3) -> zip3#2(@l2,@l3,@x,@xs) zip3#1(nil(),@l2,@l3) -> nil() zip3#2(::(@y,@ys),@l3,@x,@xs) -> zip3#3(@l3,@x,@xs,@y,@ys) zip3#2(nil(),@l3,@x,@xs) -> nil() zip3#3(::(@z,@zs),@x,@xs,@y,@ys) -> ::(tuple#3(@x,@y,@z),zip3(@xs,@ys,@zs)) zip3#3(nil(),@x,@xs,@y,@ys) -> nil() - Signature: {group3/1,group3#1/1,group3#2/2,group3#3/3,zip3/3,zip3#1/3,zip3#2/4,zip3#3/5} / {::/2,nil/0,tuple#3/3} - Obligation: innermost runtime complexity wrt. defined symbols {group3,group3#1,group3#2,group3#3,zip3,zip3#1,zip3#2 ,zip3#3} and constructors {::,nil,tuple#3} Following problems could not be solved: - Strict TRS: group3(@l) -> group3#1(@l) group3#1(::(@x,@xs)) -> group3#2(@xs,@x) group3#1(nil()) -> nil() group3#2(::(@y,@ys),@x) -> group3#3(@ys,@x,@y) group3#2(nil(),@x) -> nil() group3#3(::(@z,@zs),@x,@y) -> ::(tuple#3(@x,@y,@z),group3(@zs)) group3#3(nil(),@x,@y) -> nil() zip3(@l1,@l2,@l3) -> zip3#1(@l1,@l2,@l3) zip3#1(::(@x,@xs),@l2,@l3) -> zip3#2(@l2,@l3,@x,@xs) zip3#1(nil(),@l2,@l3) -> nil() zip3#2(::(@y,@ys),@l3,@x,@xs) -> zip3#3(@l3,@x,@xs,@y,@ys) zip3#2(nil(),@l3,@x,@xs) -> nil() zip3#3(::(@z,@zs),@x,@xs,@y,@ys) -> ::(tuple#3(@x,@y,@z),zip3(@xs,@ys,@zs)) zip3#3(nil(),@x,@xs,@y,@ys) -> nil() - Signature: {group3/1,group3#1/1,group3#2/2,group3#3/3,zip3/3,zip3#1/3,zip3#2/4,zip3#3/5} / {::/2,nil/0,tuple#3/3} - Obligation: innermost runtime complexity wrt. defined symbols {group3,group3#1,group3#2,group3#3,zip3,zip3#1,zip3#2 ,zip3#3} and constructors {::,nil,tuple#3} WORST_CASE(?,O(n^1))