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