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