WORST_CASE(Omega(n^1),?) * Step 1: Sum. WORST_CASE(Omega(n^1),?) + Considered Problem: - Strict TRS: A__ADD(z0,z1) -> c8() A__ADD(0(),z0) -> c5(MARK(z0)) A__ADD(s(z0),z1) -> c6(A__ADD(mark(z0),mark(z1)),MARK(z0)) A__ADD(s(z0),z1) -> c7(A__ADD(mark(z0),mark(z1)),MARK(z1)) A__FIB(z0) -> c(A__SEL(mark(z0),a__fib1(s(0()),s(0()))),MARK(z0)) A__FIB(z0) -> c1(A__SEL(mark(z0),a__fib1(s(0()),s(0()))),A__FIB1(s(0()),s(0()))) A__FIB(z0) -> c2() A__FIB1(z0,z1) -> c3(MARK(z0)) A__FIB1(z0,z1) -> c4() A__SEL(z0,z1) -> c12() A__SEL(0(),cons(z0,z1)) -> c9(MARK(z0)) A__SEL(s(z0),cons(z1,z2)) -> c10(A__SEL(mark(z0),mark(z2)),MARK(z0)) A__SEL(s(z0),cons(z1,z2)) -> c11(A__SEL(mark(z0),mark(z2)),MARK(z2)) MARK(0()) -> c21() MARK(add(z0,z1)) -> c18(A__ADD(mark(z0),mark(z1)),MARK(z0)) MARK(add(z0,z1)) -> c19(A__ADD(mark(z0),mark(z1)),MARK(z1)) MARK(cons(z0,z1)) -> c22(MARK(z0)) MARK(fib(z0)) -> c13(A__FIB(mark(z0)),MARK(z0)) MARK(fib1(z0,z1)) -> c16(A__FIB1(mark(z0),mark(z1)),MARK(z0)) MARK(fib1(z0,z1)) -> c17(A__FIB1(mark(z0),mark(z1)),MARK(z1)) MARK(s(z0)) -> c20(MARK(z0)) MARK(sel(z0,z1)) -> c14(A__SEL(mark(z0),mark(z1)),MARK(z0)) MARK(sel(z0,z1)) -> c15(A__SEL(mark(z0),mark(z1)),MARK(z1)) - Weak TRS: a__add(z0,z1) -> add(z0,z1) a__add(0(),z0) -> mark(z0) a__add(s(z0),z1) -> s(a__add(mark(z0),mark(z1))) a__fib(z0) -> a__sel(mark(z0),a__fib1(s(0()),s(0()))) a__fib(z0) -> fib(z0) a__fib1(z0,z1) -> cons(mark(z0),fib1(z1,add(z0,z1))) a__fib1(z0,z1) -> fib1(z0,z1) a__sel(z0,z1) -> sel(z0,z1) a__sel(0(),cons(z0,z1)) -> mark(z0) a__sel(s(z0),cons(z1,z2)) -> a__sel(mark(z0),mark(z2)) mark(0()) -> 0() mark(add(z0,z1)) -> a__add(mark(z0),mark(z1)) mark(cons(z0,z1)) -> cons(mark(z0),z1) mark(fib(z0)) -> a__fib(mark(z0)) mark(fib1(z0,z1)) -> a__fib1(mark(z0),mark(z1)) mark(s(z0)) -> s(mark(z0)) mark(sel(z0,z1)) -> a__sel(mark(z0),mark(z1)) - Signature: {A__ADD/2,A__FIB/1,A__FIB1/2,A__SEL/2,MARK/1,a__add/2,a__fib/1,a__fib1/2,a__sel/2,mark/1} / {0/0,add/2,c/2 ,c1/2,c10/2,c11/2,c12/0,c13/2,c14/2,c15/2,c16/2,c17/2,c18/2,c19/2,c2/0,c20/1,c21/0,c22/1,c3/1,c4/0,c5/1,c6/2 ,c7/2,c8/0,c9/1,cons/2,fib/1,fib1/2,s/1,sel/2} - Obligation: innermost runtime complexity wrt. defined symbols {A__ADD,A__FIB,A__FIB1,A__SEL,MARK,a__add,a__fib,a__fib1 ,a__sel,mark} and constructors {0,add,c,c1,c10,c11,c12,c13,c14,c15,c16,c17,c18,c19,c2,c20,c21,c22,c3,c4,c5 ,c6,c7,c8,c9,cons,fib,fib1,s,sel} + Applied Processor: Sum {left = someStrategy, right = someStrategy} + Details: () * Step 2: Sum. WORST_CASE(Omega(n^1),?) + Considered Problem: - Strict TRS: A__ADD(z0,z1) -> c8() A__ADD(0(),z0) -> c5(MARK(z0)) A__ADD(s(z0),z1) -> c6(A__ADD(mark(z0),mark(z1)),MARK(z0)) A__ADD(s(z0),z1) -> c7(A__ADD(mark(z0),mark(z1)),MARK(z1)) A__FIB(z0) -> c(A__SEL(mark(z0),a__fib1(s(0()),s(0()))),MARK(z0)) A__FIB(z0) -> c1(A__SEL(mark(z0),a__fib1(s(0()),s(0()))),A__FIB1(s(0()),s(0()))) A__FIB(z0) -> c2() A__FIB1(z0,z1) -> c3(MARK(z0)) A__FIB1(z0,z1) -> c4() A__SEL(z0,z1) -> c12() A__SEL(0(),cons(z0,z1)) -> c9(MARK(z0)) A__SEL(s(z0),cons(z1,z2)) -> c10(A__SEL(mark(z0),mark(z2)),MARK(z0)) A__SEL(s(z0),cons(z1,z2)) -> c11(A__SEL(mark(z0),mark(z2)),MARK(z2)) MARK(0()) -> c21() MARK(add(z0,z1)) -> c18(A__ADD(mark(z0),mark(z1)),MARK(z0)) MARK(add(z0,z1)) -> c19(A__ADD(mark(z0),mark(z1)),MARK(z1)) MARK(cons(z0,z1)) -> c22(MARK(z0)) MARK(fib(z0)) -> c13(A__FIB(mark(z0)),MARK(z0)) MARK(fib1(z0,z1)) -> c16(A__FIB1(mark(z0),mark(z1)),MARK(z0)) MARK(fib1(z0,z1)) -> c17(A__FIB1(mark(z0),mark(z1)),MARK(z1)) MARK(s(z0)) -> c20(MARK(z0)) MARK(sel(z0,z1)) -> c14(A__SEL(mark(z0),mark(z1)),MARK(z0)) MARK(sel(z0,z1)) -> c15(A__SEL(mark(z0),mark(z1)),MARK(z1)) - Weak TRS: a__add(z0,z1) -> add(z0,z1) a__add(0(),z0) -> mark(z0) a__add(s(z0),z1) -> s(a__add(mark(z0),mark(z1))) a__fib(z0) -> a__sel(mark(z0),a__fib1(s(0()),s(0()))) a__fib(z0) -> fib(z0) a__fib1(z0,z1) -> cons(mark(z0),fib1(z1,add(z0,z1))) a__fib1(z0,z1) -> fib1(z0,z1) a__sel(z0,z1) -> sel(z0,z1) a__sel(0(),cons(z0,z1)) -> mark(z0) a__sel(s(z0),cons(z1,z2)) -> a__sel(mark(z0),mark(z2)) mark(0()) -> 0() mark(add(z0,z1)) -> a__add(mark(z0),mark(z1)) mark(cons(z0,z1)) -> cons(mark(z0),z1) mark(fib(z0)) -> a__fib(mark(z0)) mark(fib1(z0,z1)) -> a__fib1(mark(z0),mark(z1)) mark(s(z0)) -> s(mark(z0)) mark(sel(z0,z1)) -> a__sel(mark(z0),mark(z1)) - Signature: {A__ADD/2,A__FIB/1,A__FIB1/2,A__SEL/2,MARK/1,a__add/2,a__fib/1,a__fib1/2,a__sel/2,mark/1} / {0/0,add/2,c/2 ,c1/2,c10/2,c11/2,c12/0,c13/2,c14/2,c15/2,c16/2,c17/2,c18/2,c19/2,c2/0,c20/1,c21/0,c22/1,c3/1,c4/0,c5/1,c6/2 ,c7/2,c8/0,c9/1,cons/2,fib/1,fib1/2,s/1,sel/2} - Obligation: innermost runtime complexity wrt. defined symbols {A__ADD,A__FIB,A__FIB1,A__SEL,MARK,a__add,a__fib,a__fib1 ,a__sel,mark} and constructors {0,add,c,c1,c10,c11,c12,c13,c14,c15,c16,c17,c18,c19,c2,c20,c21,c22,c3,c4,c5 ,c6,c7,c8,c9,cons,fib,fib1,s,sel} + Applied Processor: Sum {left = someStrategy, right = someStrategy} + Details: () * Step 3: DecreasingLoops. WORST_CASE(Omega(n^1),?) + Considered Problem: - Strict TRS: A__ADD(z0,z1) -> c8() A__ADD(0(),z0) -> c5(MARK(z0)) A__ADD(s(z0),z1) -> c6(A__ADD(mark(z0),mark(z1)),MARK(z0)) A__ADD(s(z0),z1) -> c7(A__ADD(mark(z0),mark(z1)),MARK(z1)) A__FIB(z0) -> c(A__SEL(mark(z0),a__fib1(s(0()),s(0()))),MARK(z0)) A__FIB(z0) -> c1(A__SEL(mark(z0),a__fib1(s(0()),s(0()))),A__FIB1(s(0()),s(0()))) A__FIB(z0) -> c2() A__FIB1(z0,z1) -> c3(MARK(z0)) A__FIB1(z0,z1) -> c4() A__SEL(z0,z1) -> c12() A__SEL(0(),cons(z0,z1)) -> c9(MARK(z0)) A__SEL(s(z0),cons(z1,z2)) -> c10(A__SEL(mark(z0),mark(z2)),MARK(z0)) A__SEL(s(z0),cons(z1,z2)) -> c11(A__SEL(mark(z0),mark(z2)),MARK(z2)) MARK(0()) -> c21() MARK(add(z0,z1)) -> c18(A__ADD(mark(z0),mark(z1)),MARK(z0)) MARK(add(z0,z1)) -> c19(A__ADD(mark(z0),mark(z1)),MARK(z1)) MARK(cons(z0,z1)) -> c22(MARK(z0)) MARK(fib(z0)) -> c13(A__FIB(mark(z0)),MARK(z0)) MARK(fib1(z0,z1)) -> c16(A__FIB1(mark(z0),mark(z1)),MARK(z0)) MARK(fib1(z0,z1)) -> c17(A__FIB1(mark(z0),mark(z1)),MARK(z1)) MARK(s(z0)) -> c20(MARK(z0)) MARK(sel(z0,z1)) -> c14(A__SEL(mark(z0),mark(z1)),MARK(z0)) MARK(sel(z0,z1)) -> c15(A__SEL(mark(z0),mark(z1)),MARK(z1)) - Weak TRS: a__add(z0,z1) -> add(z0,z1) a__add(0(),z0) -> mark(z0) a__add(s(z0),z1) -> s(a__add(mark(z0),mark(z1))) a__fib(z0) -> a__sel(mark(z0),a__fib1(s(0()),s(0()))) a__fib(z0) -> fib(z0) a__fib1(z0,z1) -> cons(mark(z0),fib1(z1,add(z0,z1))) a__fib1(z0,z1) -> fib1(z0,z1) a__sel(z0,z1) -> sel(z0,z1) a__sel(0(),cons(z0,z1)) -> mark(z0) a__sel(s(z0),cons(z1,z2)) -> a__sel(mark(z0),mark(z2)) mark(0()) -> 0() mark(add(z0,z1)) -> a__add(mark(z0),mark(z1)) mark(cons(z0,z1)) -> cons(mark(z0),z1) mark(fib(z0)) -> a__fib(mark(z0)) mark(fib1(z0,z1)) -> a__fib1(mark(z0),mark(z1)) mark(s(z0)) -> s(mark(z0)) mark(sel(z0,z1)) -> a__sel(mark(z0),mark(z1)) - Signature: {A__ADD/2,A__FIB/1,A__FIB1/2,A__SEL/2,MARK/1,a__add/2,a__fib/1,a__fib1/2,a__sel/2,mark/1} / {0/0,add/2,c/2 ,c1/2,c10/2,c11/2,c12/0,c13/2,c14/2,c15/2,c16/2,c17/2,c18/2,c19/2,c2/0,c20/1,c21/0,c22/1,c3/1,c4/0,c5/1,c6/2 ,c7/2,c8/0,c9/1,cons/2,fib/1,fib1/2,s/1,sel/2} - Obligation: innermost runtime complexity wrt. defined symbols {A__ADD,A__FIB,A__FIB1,A__SEL,MARK,a__add,a__fib,a__fib1 ,a__sel,mark} and constructors {0,add,c,c1,c10,c11,c12,c13,c14,c15,c16,c17,c18,c19,c2,c20,c21,c22,c3,c4,c5 ,c6,c7,c8,c9,cons,fib,fib1,s,sel} + Applied Processor: DecreasingLoops {bound = AnyLoop, narrow = 10} + Details: The system has following decreasing Loops: MARK(x){x -> add(x,y)} = MARK(add(x,y)) ->^+ c18(A__ADD(mark(x),mark(y)),MARK(x)) = C[MARK(x) = MARK(x){}] WORST_CASE(Omega(n^1),?)