* Step 1: Sum WORST_CASE(Omega(n^1),?) + Considered Problem: - Strict TRS: if(false(),b,x,y) -> if2(b,x,y) if(true(),b,x,y) -> log_undefined() if2(false(),x,y) -> log2(quot(x,s(s(0()))),y) if2(true(),x,s(y)) -> y inc(0()) -> 0() inc(s(x)) -> s(inc(x)) le(0(),y) -> true() le(s(x),0()) -> false() le(s(x),s(y)) -> le(x,y) log(x) -> log2(x,0()) log2(x,y) -> if(le(x,0()),le(x,s(0())),x,inc(y)) minus(x,0()) -> x minus(0(),y) -> 0() minus(s(x),s(y)) -> minus(x,y) quot(0(),s(y)) -> 0() quot(s(x),s(y)) -> s(quot(minus(x,y),s(y))) - Signature: {if/4,if2/3,inc/1,le/2,log/1,log2/2,minus/2,quot/2} / {0/0,false/0,log_undefined/0,s/1,true/0} - Obligation: innermost runtime complexity wrt. defined symbols {if,if2,inc,le,log,log2,minus,quot} and constructors {0 ,false,log_undefined,s,true} + Applied Processor: Sum {left = someStrategy, right = someStrategy} + Details: () * Step 2: DecreasingLoops WORST_CASE(Omega(n^1),?) + Considered Problem: - Strict TRS: if(false(),b,x,y) -> if2(b,x,y) if(true(),b,x,y) -> log_undefined() if2(false(),x,y) -> log2(quot(x,s(s(0()))),y) if2(true(),x,s(y)) -> y inc(0()) -> 0() inc(s(x)) -> s(inc(x)) le(0(),y) -> true() le(s(x),0()) -> false() le(s(x),s(y)) -> le(x,y) log(x) -> log2(x,0()) log2(x,y) -> if(le(x,0()),le(x,s(0())),x,inc(y)) minus(x,0()) -> x minus(0(),y) -> 0() minus(s(x),s(y)) -> minus(x,y) quot(0(),s(y)) -> 0() quot(s(x),s(y)) -> s(quot(minus(x,y),s(y))) - Signature: {if/4,if2/3,inc/1,le/2,log/1,log2/2,minus/2,quot/2} / {0/0,false/0,log_undefined/0,s/1,true/0} - Obligation: innermost runtime complexity wrt. defined symbols {if,if2,inc,le,log,log2,minus,quot} and constructors {0 ,false,log_undefined,s,true} + Applied Processor: DecreasingLoops {bound = AnyLoop, narrow = 10} + Details: The system has following decreasing Loops: inc(x){x -> s(x)} = inc(s(x)) ->^+ s(inc(x)) = C[inc(x) = inc(x){}] WORST_CASE(Omega(n^1),?)