WORST_CASE(Omega(n^1),?) * Step 1: Sum. WORST_CASE(Omega(n^1),?) + Considered Problem: - Strict TRS: FROM(z0) -> c(FROM(s(z0))) MINUS(z0,0()) -> c3() MINUS(s(z0),s(z1)) -> c4(MINUS(z0,z1)) QUOT(0(),s(z0)) -> c5() QUOT(s(z0),s(z1)) -> c6(QUOT(minus(z0,z1),s(z1)),MINUS(z0,z1)) SEL(0(),cons(z0,z1)) -> c1() SEL(s(z0),cons(z1,z2)) -> c2(SEL(z0,z2)) ZWQUOT(z0,nil()) -> c7() ZWQUOT(cons(z0,z1),cons(z2,z3)) -> c10(ZWQUOT(z1,z3)) ZWQUOT(cons(z0,z1),cons(z2,z3)) -> c9(QUOT(z0,z2)) ZWQUOT(nil(),z0) -> c8() - Weak TRS: from(z0) -> cons(z0,from(s(z0))) minus(z0,0()) -> 0() minus(s(z0),s(z1)) -> minus(z0,z1) quot(0(),s(z0)) -> 0() quot(s(z0),s(z1)) -> s(quot(minus(z0,z1),s(z1))) sel(0(),cons(z0,z1)) -> z0 sel(s(z0),cons(z1,z2)) -> sel(z0,z2) zWquot(z0,nil()) -> nil() zWquot(cons(z0,z1),cons(z2,z3)) -> cons(quot(z0,z2),zWquot(z1,z3)) zWquot(nil(),z0) -> nil() - Signature: {FROM/1,MINUS/2,QUOT/2,SEL/2,ZWQUOT/2,from/1,minus/2,quot/2,sel/2,zWquot/2} / {0/0,c/1,c1/0,c10/1,c2/1,c3/0 ,c4/1,c5/0,c6/2,c7/0,c8/0,c9/1,cons/2,nil/0,s/1} - Obligation: innermost runtime complexity wrt. defined symbols {FROM,MINUS,QUOT,SEL,ZWQUOT,from,minus,quot,sel ,zWquot} and constructors {0,c,c1,c10,c2,c3,c4,c5,c6,c7,c8,c9,cons,nil,s} + Applied Processor: Sum {left = someStrategy, right = someStrategy} + Details: () * Step 2: Sum. WORST_CASE(Omega(n^1),?) + Considered Problem: - Strict TRS: FROM(z0) -> c(FROM(s(z0))) MINUS(z0,0()) -> c3() MINUS(s(z0),s(z1)) -> c4(MINUS(z0,z1)) QUOT(0(),s(z0)) -> c5() QUOT(s(z0),s(z1)) -> c6(QUOT(minus(z0,z1),s(z1)),MINUS(z0,z1)) SEL(0(),cons(z0,z1)) -> c1() SEL(s(z0),cons(z1,z2)) -> c2(SEL(z0,z2)) ZWQUOT(z0,nil()) -> c7() ZWQUOT(cons(z0,z1),cons(z2,z3)) -> c10(ZWQUOT(z1,z3)) ZWQUOT(cons(z0,z1),cons(z2,z3)) -> c9(QUOT(z0,z2)) ZWQUOT(nil(),z0) -> c8() - Weak TRS: from(z0) -> cons(z0,from(s(z0))) minus(z0,0()) -> 0() minus(s(z0),s(z1)) -> minus(z0,z1) quot(0(),s(z0)) -> 0() quot(s(z0),s(z1)) -> s(quot(minus(z0,z1),s(z1))) sel(0(),cons(z0,z1)) -> z0 sel(s(z0),cons(z1,z2)) -> sel(z0,z2) zWquot(z0,nil()) -> nil() zWquot(cons(z0,z1),cons(z2,z3)) -> cons(quot(z0,z2),zWquot(z1,z3)) zWquot(nil(),z0) -> nil() - Signature: {FROM/1,MINUS/2,QUOT/2,SEL/2,ZWQUOT/2,from/1,minus/2,quot/2,sel/2,zWquot/2} / {0/0,c/1,c1/0,c10/1,c2/1,c3/0 ,c4/1,c5/0,c6/2,c7/0,c8/0,c9/1,cons/2,nil/0,s/1} - Obligation: innermost runtime complexity wrt. defined symbols {FROM,MINUS,QUOT,SEL,ZWQUOT,from,minus,quot,sel ,zWquot} and constructors {0,c,c1,c10,c2,c3,c4,c5,c6,c7,c8,c9,cons,nil,s} + Applied Processor: Sum {left = someStrategy, right = someStrategy} + Details: () * Step 3: DecreasingLoops. WORST_CASE(Omega(n^1),?) + Considered Problem: - Strict TRS: FROM(z0) -> c(FROM(s(z0))) MINUS(z0,0()) -> c3() MINUS(s(z0),s(z1)) -> c4(MINUS(z0,z1)) QUOT(0(),s(z0)) -> c5() QUOT(s(z0),s(z1)) -> c6(QUOT(minus(z0,z1),s(z1)),MINUS(z0,z1)) SEL(0(),cons(z0,z1)) -> c1() SEL(s(z0),cons(z1,z2)) -> c2(SEL(z0,z2)) ZWQUOT(z0,nil()) -> c7() ZWQUOT(cons(z0,z1),cons(z2,z3)) -> c10(ZWQUOT(z1,z3)) ZWQUOT(cons(z0,z1),cons(z2,z3)) -> c9(QUOT(z0,z2)) ZWQUOT(nil(),z0) -> c8() - Weak TRS: from(z0) -> cons(z0,from(s(z0))) minus(z0,0()) -> 0() minus(s(z0),s(z1)) -> minus(z0,z1) quot(0(),s(z0)) -> 0() quot(s(z0),s(z1)) -> s(quot(minus(z0,z1),s(z1))) sel(0(),cons(z0,z1)) -> z0 sel(s(z0),cons(z1,z2)) -> sel(z0,z2) zWquot(z0,nil()) -> nil() zWquot(cons(z0,z1),cons(z2,z3)) -> cons(quot(z0,z2),zWquot(z1,z3)) zWquot(nil(),z0) -> nil() - Signature: {FROM/1,MINUS/2,QUOT/2,SEL/2,ZWQUOT/2,from/1,minus/2,quot/2,sel/2,zWquot/2} / {0/0,c/1,c1/0,c10/1,c2/1,c3/0 ,c4/1,c5/0,c6/2,c7/0,c8/0,c9/1,cons/2,nil/0,s/1} - Obligation: innermost runtime complexity wrt. defined symbols {FROM,MINUS,QUOT,SEL,ZWQUOT,from,minus,quot,sel ,zWquot} and constructors {0,c,c1,c10,c2,c3,c4,c5,c6,c7,c8,c9,cons,nil,s} + Applied Processor: DecreasingLoops {bound = AnyLoop, narrow = 10} + Details: The system has following decreasing Loops: MINUS(x,y){x -> s(x),y -> s(y)} = MINUS(s(x),s(y)) ->^+ c4(MINUS(x,y)) = C[MINUS(x,y) = MINUS(x,y){}] WORST_CASE(Omega(n^1),?)