WORST_CASE(?,O(n^2)) * Step 1: WeightGap WORST_CASE(?,O(n^2)) + Considered Problem: - Strict TRS: loop(Cons(x,xs),Nil(),pp,ss) -> False() loop(Cons(x',xs'),Cons(x,xs),pp,ss) -> loop[Ite](!EQ(x',x),Cons(x',xs'),Cons(x,xs),pp,ss) loop(Nil(),s,pp,ss) -> True() match1(p,s) -> loop(p,s,p,s) - Weak TRS: !EQ(0(),0()) -> True() !EQ(0(),S(y)) -> False() !EQ(S(x),0()) -> False() !EQ(S(x),S(y)) -> !EQ(x,y) loop[Ite](False(),p,s,pp,Cons(x,xs)) -> loop(pp,xs,pp,xs) loop[Ite](True(),Cons(x',xs'),Cons(x,xs),pp,ss) -> loop(xs',xs,pp,ss) - Signature: {!EQ/2,loop/4,loop[Ite]/5,match1/2} / {0/0,Cons/2,False/0,Nil/0,S/1,True/0} - Obligation: innermost runtime complexity wrt. defined symbols {!EQ,loop,loop[Ite],match1} and constructors {0,Cons,False ,Nil,S,True} + Applied Processor: WeightGap {wgDimension = 1, wgDegree = 1, wgKind = Algebraic, wgUArgs = UArgs, wgOn = WgOnAny} + Details: The weightgap principle applies using the following nonconstant growth matrix-interpretation: We apply a matrix interpretation of kind constructor based matrix interpretation: The following argument positions are considered usable: uargs(loop[Ite]) = {1} Following symbols are considered usable: all TcT has computed the following interpretation: p(!EQ) = [2] p(0) = [0] p(Cons) = [1] x1 + [1] x2 + [0] p(False) = [2] p(Nil) = [0] p(S) = [1] x1 + [0] p(True) = [2] p(loop) = [2] p(loop[Ite]) = [1] x1 + [0] p(match1) = [3] Following rules are strictly oriented: match1(p,s) = [3] > [2] = loop(p,s,p,s) Following rules are (at-least) weakly oriented: !EQ(0(),0()) = [2] >= [2] = True() !EQ(0(),S(y)) = [2] >= [2] = False() !EQ(S(x),0()) = [2] >= [2] = False() !EQ(S(x),S(y)) = [2] >= [2] = !EQ(x,y) loop(Cons(x,xs),Nil(),pp,ss) = [2] >= [2] = False() loop(Cons(x',xs'),Cons(x,xs),pp,ss) = [2] >= [2] = loop[Ite](!EQ(x',x),Cons(x',xs'),Cons(x,xs),pp,ss) loop(Nil(),s,pp,ss) = [2] >= [2] = True() loop[Ite](False(),p,s,pp,Cons(x,xs)) = [2] >= [2] = loop(pp,xs,pp,xs) loop[Ite](True(),Cons(x',xs'),Cons(x,xs),pp,ss) = [2] >= [2] = loop(xs',xs,pp,ss) Further, it can be verified that all rules not oriented are covered by the weightgap condition. * Step 2: NaturalMI WORST_CASE(?,O(n^2)) + Considered Problem: - Strict TRS: loop(Cons(x,xs),Nil(),pp,ss) -> False() loop(Cons(x',xs'),Cons(x,xs),pp,ss) -> loop[Ite](!EQ(x',x),Cons(x',xs'),Cons(x,xs),pp,ss) loop(Nil(),s,pp,ss) -> True() - Weak TRS: !EQ(0(),0()) -> True() !EQ(0(),S(y)) -> False() !EQ(S(x),0()) -> False() !EQ(S(x),S(y)) -> !EQ(x,y) loop[Ite](False(),p,s,pp,Cons(x,xs)) -> loop(pp,xs,pp,xs) loop[Ite](True(),Cons(x',xs'),Cons(x,xs),pp,ss) -> loop(xs',xs,pp,ss) match1(p,s) -> loop(p,s,p,s) - Signature: {!EQ/2,loop/4,loop[Ite]/5,match1/2} / {0/0,Cons/2,False/0,Nil/0,S/1,True/0} - Obligation: innermost runtime complexity wrt. defined symbols {!EQ,loop,loop[Ite],match1} and constructors {0,Cons,False ,Nil,S,True} + Applied Processor: NaturalMI {miDimension = 1, miDegree = 1, miKind = Algebraic, uargs = UArgs, urules = URules, selector = Just any strict-rules} + Details: We apply a matrix interpretation of kind constructor based matrix interpretation: The following argument positions are considered usable: uargs(loop[Ite]) = {1} Following symbols are considered usable: {!EQ,loop,loop[Ite],match1} TcT has computed the following interpretation: p(!EQ) = [4] p(0) = [8] p(Cons) = [4] p(False) = [4] p(Nil) = [1] p(S) = [0] p(True) = [4] p(loop) = [12] p(loop[Ite]) = [2] x1 + [4] p(match1) = [12] Following rules are strictly oriented: loop(Cons(x,xs),Nil(),pp,ss) = [12] > [4] = False() loop(Nil(),s,pp,ss) = [12] > [4] = True() Following rules are (at-least) weakly oriented: !EQ(0(),0()) = [4] >= [4] = True() !EQ(0(),S(y)) = [4] >= [4] = False() !EQ(S(x),0()) = [4] >= [4] = False() !EQ(S(x),S(y)) = [4] >= [4] = !EQ(x,y) loop(Cons(x',xs'),Cons(x,xs),pp,ss) = [12] >= [12] = loop[Ite](!EQ(x',x),Cons(x',xs'),Cons(x,xs),pp,ss) loop[Ite](False(),p,s,pp,Cons(x,xs)) = [12] >= [12] = loop(pp,xs,pp,xs) loop[Ite](True(),Cons(x',xs'),Cons(x,xs),pp,ss) = [12] >= [12] = loop(xs',xs,pp,ss) match1(p,s) = [12] >= [12] = loop(p,s,p,s) * Step 3: NaturalMI WORST_CASE(?,O(n^2)) + Considered Problem: - Strict TRS: loop(Cons(x',xs'),Cons(x,xs),pp,ss) -> loop[Ite](!EQ(x',x),Cons(x',xs'),Cons(x,xs),pp,ss) - Weak TRS: !EQ(0(),0()) -> True() !EQ(0(),S(y)) -> False() !EQ(S(x),0()) -> False() !EQ(S(x),S(y)) -> !EQ(x,y) loop(Cons(x,xs),Nil(),pp,ss) -> False() loop(Nil(),s,pp,ss) -> True() loop[Ite](False(),p,s,pp,Cons(x,xs)) -> loop(pp,xs,pp,xs) loop[Ite](True(),Cons(x',xs'),Cons(x,xs),pp,ss) -> loop(xs',xs,pp,ss) match1(p,s) -> loop(p,s,p,s) - Signature: {!EQ/2,loop/4,loop[Ite]/5,match1/2} / {0/0,Cons/2,False/0,Nil/0,S/1,True/0} - Obligation: innermost runtime complexity wrt. defined symbols {!EQ,loop,loop[Ite],match1} and constructors {0,Cons,False ,Nil,S,True} + Applied Processor: NaturalMI {miDimension = 2, miDegree = 2, miKind = Algebraic, uargs = UArgs, urules = URules, selector = Just any strict-rules} + Details: We apply a matrix interpretation of kind constructor based matrix interpretation: The following argument positions are considered usable: uargs(loop[Ite]) = {1} Following symbols are considered usable: {!EQ,loop,loop[Ite],match1} TcT has computed the following interpretation: p(!EQ) = [0] [0] p(0) = [4] [0] p(Cons) = [0 0] x1 + [1 2] x2 + [1] [0 1] [0 1] [4] p(False) = [0] [0] p(Nil) = [1] [3] p(S) = [1 4] x1 + [0] [0 1] [0] p(True) = [0] [0] p(loop) = [0 2] x2 + [1 0] x4 + [1] [0 0] [0 1] [4] p(loop[Ite]) = [4 0] x1 + [0 2] x3 + [1 0] x5 + [0] [4 1] [0 0] [0 1] [4] p(match1) = [0 0] x1 + [1 4] x2 + [1] [1 0] [0 1] [6] Following rules are strictly oriented: loop(Cons(x',xs'),Cons(x,xs),pp,ss) = [1 0] ss + [0 2] x + [0 2] xs + [9] [0 1] [0 0] [0 0] [4] > [1 0] ss + [0 2] x + [0 2] xs + [8] [0 1] [0 0] [0 0] [4] = loop[Ite](!EQ(x',x),Cons(x',xs'),Cons(x,xs),pp,ss) Following rules are (at-least) weakly oriented: !EQ(0(),0()) = [0] [0] >= [0] [0] = True() !EQ(0(),S(y)) = [0] [0] >= [0] [0] = False() !EQ(S(x),0()) = [0] [0] >= [0] [0] = False() !EQ(S(x),S(y)) = [0] [0] >= [0] [0] = !EQ(x,y) loop(Cons(x,xs),Nil(),pp,ss) = [1 0] ss + [7] [0 1] [4] >= [0] [0] = False() loop(Nil(),s,pp,ss) = [0 2] s + [1 0] ss + [1] [0 0] [0 1] [4] >= [0] [0] = True() loop[Ite](False(),p,s,pp,Cons(x,xs)) = [0 2] s + [0 0] x + [1 2] xs + [1] [0 0] [0 1] [0 1] [8] >= [1 2] xs + [1] [0 1] [4] = loop(pp,xs,pp,xs) loop[Ite](True(),Cons(x',xs'),Cons(x,xs),pp,ss) = [1 0] ss + [0 2] x + [0 2] xs + [8] [0 1] [0 0] [0 0] [4] >= [1 0] ss + [0 2] xs + [1] [0 1] [0 0] [4] = loop(xs',xs,pp,ss) match1(p,s) = [0 0] p + [1 4] s + [1] [1 0] [0 1] [6] >= [1 2] s + [1] [0 1] [4] = loop(p,s,p,s) * Step 4: EmptyProcessor WORST_CASE(?,O(1)) + Considered Problem: - Weak TRS: !EQ(0(),0()) -> True() !EQ(0(),S(y)) -> False() !EQ(S(x),0()) -> False() !EQ(S(x),S(y)) -> !EQ(x,y) loop(Cons(x,xs),Nil(),pp,ss) -> False() loop(Cons(x',xs'),Cons(x,xs),pp,ss) -> loop[Ite](!EQ(x',x),Cons(x',xs'),Cons(x,xs),pp,ss) loop(Nil(),s,pp,ss) -> True() loop[Ite](False(),p,s,pp,Cons(x,xs)) -> loop(pp,xs,pp,xs) loop[Ite](True(),Cons(x',xs'),Cons(x,xs),pp,ss) -> loop(xs',xs,pp,ss) match1(p,s) -> loop(p,s,p,s) - Signature: {!EQ/2,loop/4,loop[Ite]/5,match1/2} / {0/0,Cons/2,False/0,Nil/0,S/1,True/0} - Obligation: innermost runtime complexity wrt. defined symbols {!EQ,loop,loop[Ite],match1} and constructors {0,Cons,False ,Nil,S,True} + Applied Processor: EmptyProcessor + Details: The problem is already closed. The intended complexity is O(1). WORST_CASE(?,O(n^2))