WORST_CASE(Omega(n^1),?) * Step 1: Sum. WORST_CASE(Omega(n^1),?) + Considered Problem: - Strict TRS: AND(z0,false()) -> c16() AND(false(),z0) -> c15() AND(true(),true()) -> c14() COND1(true(),z0,z1) -> c(COND2(gr(z0,z1),z0,z1),GR(z0,z1)) COND2(false(),z0,z1) -> c2(COND4(gr(z1,0()),z0,z1),GR(z1,0())) COND2(true(),z0,z1) -> c1(COND3(gr(z0,0()),z0,z1),GR(z0,0())) COND3(false(),z0,z1) -> c5(COND1(and(gr(z0,0()),gr(z1,0())),z0,z1),AND(gr(z0,0()),gr(z1,0())),GR(z0,0())) COND3(false(),z0,z1) -> c6(COND1(and(gr(z0,0()),gr(z1,0())),z0,z1),AND(gr(z0,0()),gr(z1,0())),GR(z1,0())) COND3(true(),z0,z1) -> c3(COND3(gr(z0,0()),p(z0),z1),GR(z0,0())) COND3(true(),z0,z1) -> c4(COND3(gr(z0,0()),p(z0),z1),P(z0)) COND4(false(),z0,z1) -> c10(COND1(and(gr(z0,0()),gr(z1,0())),z0,z1),AND(gr(z0,0()),gr(z1,0())),GR(z1,0())) COND4(false(),z0,z1) -> c9(COND1(and(gr(z0,0()),gr(z1,0())),z0,z1),AND(gr(z0,0()),gr(z1,0())),GR(z0,0())) COND4(true(),z0,z1) -> c7(COND4(gr(z1,0()),z0,p(z1)),GR(z1,0())) COND4(true(),z0,z1) -> c8(COND4(gr(z1,0()),z0,p(z1)),P(z1)) GR(0(),z0) -> c11() GR(s(z0),0()) -> c12() GR(s(z0),s(z1)) -> c13(GR(z0,z1)) P(0()) -> c17() P(s(z0)) -> c18() - Weak TRS: and(z0,false()) -> false() and(false(),z0) -> false() and(true(),true()) -> true() cond1(true(),z0,z1) -> cond2(gr(z0,z1),z0,z1) cond2(false(),z0,z1) -> cond4(gr(z1,0()),z0,z1) cond2(true(),z0,z1) -> cond3(gr(z0,0()),z0,z1) cond3(false(),z0,z1) -> cond1(and(gr(z0,0()),gr(z1,0())),z0,z1) cond3(true(),z0,z1) -> cond3(gr(z0,0()),p(z0),z1) cond4(false(),z0,z1) -> cond1(and(gr(z0,0()),gr(z1,0())),z0,z1) cond4(true(),z0,z1) -> cond4(gr(z1,0()),z0,p(z1)) gr(0(),z0) -> false() gr(s(z0),0()) -> true() gr(s(z0),s(z1)) -> gr(z0,z1) p(0()) -> 0() p(s(z0)) -> z0 - Signature: {AND/2,COND1/3,COND2/3,COND3/3,COND4/3,GR/2,P/1,and/2,cond1/3,cond2/3,cond3/3,cond4/3,gr/2,p/1} / {0/0,c/2 ,c1/2,c10/3,c11/0,c12/0,c13/1,c14/0,c15/0,c16/0,c17/0,c18/0,c2/2,c3/2,c4/2,c5/3,c6/3,c7/2,c8/2,c9/3,false/0 ,s/1,true/0} - Obligation: innermost runtime complexity wrt. defined symbols {AND,COND1,COND2,COND3,COND4,GR,P,and,cond1,cond2,cond3 ,cond4,gr,p} and constructors {0,c,c1,c10,c11,c12,c13,c14,c15,c16,c17,c18,c2,c3,c4,c5,c6,c7,c8,c9,false,s ,true} + Applied Processor: Sum {left = someStrategy, right = someStrategy} + Details: () * Step 2: Sum. WORST_CASE(Omega(n^1),?) + Considered Problem: - Strict TRS: AND(z0,false()) -> c16() AND(false(),z0) -> c15() AND(true(),true()) -> c14() COND1(true(),z0,z1) -> c(COND2(gr(z0,z1),z0,z1),GR(z0,z1)) COND2(false(),z0,z1) -> c2(COND4(gr(z1,0()),z0,z1),GR(z1,0())) COND2(true(),z0,z1) -> c1(COND3(gr(z0,0()),z0,z1),GR(z0,0())) COND3(false(),z0,z1) -> c5(COND1(and(gr(z0,0()),gr(z1,0())),z0,z1),AND(gr(z0,0()),gr(z1,0())),GR(z0,0())) COND3(false(),z0,z1) -> c6(COND1(and(gr(z0,0()),gr(z1,0())),z0,z1),AND(gr(z0,0()),gr(z1,0())),GR(z1,0())) COND3(true(),z0,z1) -> c3(COND3(gr(z0,0()),p(z0),z1),GR(z0,0())) COND3(true(),z0,z1) -> c4(COND3(gr(z0,0()),p(z0),z1),P(z0)) COND4(false(),z0,z1) -> c10(COND1(and(gr(z0,0()),gr(z1,0())),z0,z1),AND(gr(z0,0()),gr(z1,0())),GR(z1,0())) COND4(false(),z0,z1) -> c9(COND1(and(gr(z0,0()),gr(z1,0())),z0,z1),AND(gr(z0,0()),gr(z1,0())),GR(z0,0())) COND4(true(),z0,z1) -> c7(COND4(gr(z1,0()),z0,p(z1)),GR(z1,0())) COND4(true(),z0,z1) -> c8(COND4(gr(z1,0()),z0,p(z1)),P(z1)) GR(0(),z0) -> c11() GR(s(z0),0()) -> c12() GR(s(z0),s(z1)) -> c13(GR(z0,z1)) P(0()) -> c17() P(s(z0)) -> c18() - Weak TRS: and(z0,false()) -> false() and(false(),z0) -> false() and(true(),true()) -> true() cond1(true(),z0,z1) -> cond2(gr(z0,z1),z0,z1) cond2(false(),z0,z1) -> cond4(gr(z1,0()),z0,z1) cond2(true(),z0,z1) -> cond3(gr(z0,0()),z0,z1) cond3(false(),z0,z1) -> cond1(and(gr(z0,0()),gr(z1,0())),z0,z1) cond3(true(),z0,z1) -> cond3(gr(z0,0()),p(z0),z1) cond4(false(),z0,z1) -> cond1(and(gr(z0,0()),gr(z1,0())),z0,z1) cond4(true(),z0,z1) -> cond4(gr(z1,0()),z0,p(z1)) gr(0(),z0) -> false() gr(s(z0),0()) -> true() gr(s(z0),s(z1)) -> gr(z0,z1) p(0()) -> 0() p(s(z0)) -> z0 - Signature: {AND/2,COND1/3,COND2/3,COND3/3,COND4/3,GR/2,P/1,and/2,cond1/3,cond2/3,cond3/3,cond4/3,gr/2,p/1} / {0/0,c/2 ,c1/2,c10/3,c11/0,c12/0,c13/1,c14/0,c15/0,c16/0,c17/0,c18/0,c2/2,c3/2,c4/2,c5/3,c6/3,c7/2,c8/2,c9/3,false/0 ,s/1,true/0} - Obligation: innermost runtime complexity wrt. defined symbols {AND,COND1,COND2,COND3,COND4,GR,P,and,cond1,cond2,cond3 ,cond4,gr,p} and constructors {0,c,c1,c10,c11,c12,c13,c14,c15,c16,c17,c18,c2,c3,c4,c5,c6,c7,c8,c9,false,s ,true} + Applied Processor: Sum {left = someStrategy, right = someStrategy} + Details: () * Step 3: DecreasingLoops. WORST_CASE(Omega(n^1),?) + Considered Problem: - Strict TRS: AND(z0,false()) -> c16() AND(false(),z0) -> c15() AND(true(),true()) -> c14() COND1(true(),z0,z1) -> c(COND2(gr(z0,z1),z0,z1),GR(z0,z1)) COND2(false(),z0,z1) -> c2(COND4(gr(z1,0()),z0,z1),GR(z1,0())) COND2(true(),z0,z1) -> c1(COND3(gr(z0,0()),z0,z1),GR(z0,0())) COND3(false(),z0,z1) -> c5(COND1(and(gr(z0,0()),gr(z1,0())),z0,z1),AND(gr(z0,0()),gr(z1,0())),GR(z0,0())) COND3(false(),z0,z1) -> c6(COND1(and(gr(z0,0()),gr(z1,0())),z0,z1),AND(gr(z0,0()),gr(z1,0())),GR(z1,0())) COND3(true(),z0,z1) -> c3(COND3(gr(z0,0()),p(z0),z1),GR(z0,0())) COND3(true(),z0,z1) -> c4(COND3(gr(z0,0()),p(z0),z1),P(z0)) COND4(false(),z0,z1) -> c10(COND1(and(gr(z0,0()),gr(z1,0())),z0,z1),AND(gr(z0,0()),gr(z1,0())),GR(z1,0())) COND4(false(),z0,z1) -> c9(COND1(and(gr(z0,0()),gr(z1,0())),z0,z1),AND(gr(z0,0()),gr(z1,0())),GR(z0,0())) COND4(true(),z0,z1) -> c7(COND4(gr(z1,0()),z0,p(z1)),GR(z1,0())) COND4(true(),z0,z1) -> c8(COND4(gr(z1,0()),z0,p(z1)),P(z1)) GR(0(),z0) -> c11() GR(s(z0),0()) -> c12() GR(s(z0),s(z1)) -> c13(GR(z0,z1)) P(0()) -> c17() P(s(z0)) -> c18() - Weak TRS: and(z0,false()) -> false() and(false(),z0) -> false() and(true(),true()) -> true() cond1(true(),z0,z1) -> cond2(gr(z0,z1),z0,z1) cond2(false(),z0,z1) -> cond4(gr(z1,0()),z0,z1) cond2(true(),z0,z1) -> cond3(gr(z0,0()),z0,z1) cond3(false(),z0,z1) -> cond1(and(gr(z0,0()),gr(z1,0())),z0,z1) cond3(true(),z0,z1) -> cond3(gr(z0,0()),p(z0),z1) cond4(false(),z0,z1) -> cond1(and(gr(z0,0()),gr(z1,0())),z0,z1) cond4(true(),z0,z1) -> cond4(gr(z1,0()),z0,p(z1)) gr(0(),z0) -> false() gr(s(z0),0()) -> true() gr(s(z0),s(z1)) -> gr(z0,z1) p(0()) -> 0() p(s(z0)) -> z0 - Signature: {AND/2,COND1/3,COND2/3,COND3/3,COND4/3,GR/2,P/1,and/2,cond1/3,cond2/3,cond3/3,cond4/3,gr/2,p/1} / {0/0,c/2 ,c1/2,c10/3,c11/0,c12/0,c13/1,c14/0,c15/0,c16/0,c17/0,c18/0,c2/2,c3/2,c4/2,c5/3,c6/3,c7/2,c8/2,c9/3,false/0 ,s/1,true/0} - Obligation: innermost runtime complexity wrt. defined symbols {AND,COND1,COND2,COND3,COND4,GR,P,and,cond1,cond2,cond3 ,cond4,gr,p} and constructors {0,c,c1,c10,c11,c12,c13,c14,c15,c16,c17,c18,c2,c3,c4,c5,c6,c7,c8,c9,false,s ,true} + Applied Processor: DecreasingLoops {bound = AnyLoop, narrow = 10} + Details: The system has following decreasing Loops: GR(x,y){x -> s(x),y -> s(y)} = GR(s(x),s(y)) ->^+ c13(GR(x,y)) = C[GR(x,y) = GR(x,y){}] WORST_CASE(Omega(n^1),?)