```* Step 1: Bounds WORST_CASE(?,O(n^1))
+ Considered Problem:
- Strict TRS:
a__f(X) -> f(X)
a__f(0()) -> cons(0(),f(s(0())))
a__f(s(0())) -> a__f(a__p(s(0())))
a__p(X) -> p(X)
a__p(s(0())) -> 0()
mark(0()) -> 0()
mark(cons(X1,X2)) -> cons(mark(X1),X2)
mark(f(X)) -> a__f(mark(X))
mark(p(X)) -> a__p(mark(X))
mark(s(X)) -> s(mark(X))
- Signature:
{a__f/1,a__p/1,mark/1} / {0/0,cons/2,f/1,p/1,s/1}
- Obligation:
innermost runtime complexity wrt. defined symbols {a__f,a__p,mark} and constructors {0,cons,f,p,s}
+ Applied Processor:
Bounds {initialAutomaton = minimal, enrichment = match}
+ Details:
The problem is match-bounded by 3.
The enriched problem is compatible with follwoing automaton.
0_0() -> 2
0_1() -> 1
0_1() -> 3
0_1() -> 6
0_1() -> 8
0_2() -> 1
0_2() -> 7
0_2() -> 8
0_3() -> 11
a__f_0(2) -> 1
a__f_1(7) -> 1
a__f_1(8) -> 1
a__f_1(8) -> 8
a__f_2(11) -> 1
a__f_2(11) -> 8
a__p_0(2) -> 1
a__p_1(5) -> 7
a__p_1(8) -> 1
a__p_1(8) -> 8
a__p_2(10) -> 11
cons_0(2,2) -> 2
cons_1(3,4) -> 1
cons_1(8,2) -> 1
cons_1(8,2) -> 8
cons_2(7,9) -> 1
cons_2(7,9) -> 8
cons_3(11,12) -> 1
cons_3(11,12) -> 8
f_0(2) -> 2
f_1(2) -> 1
f_1(5) -> 4
f_2(7) -> 1
f_2(8) -> 1
f_2(8) -> 8
f_2(10) -> 9
f_3(11) -> 1
f_3(11) -> 8
f_3(13) -> 12
mark_0(2) -> 1
mark_1(2) -> 8
p_0(2) -> 2
p_1(2) -> 1
p_2(5) -> 7
p_2(8) -> 1
p_2(8) -> 8
p_3(10) -> 11
s_0(2) -> 2
s_1(6) -> 5
s_1(8) -> 1
s_1(8) -> 8
s_2(7) -> 10
s_3(11) -> 13
* Step 2: EmptyProcessor WORST_CASE(?,O(1))
+ Considered Problem:
- Weak TRS:
a__f(X) -> f(X)
a__f(0()) -> cons(0(),f(s(0())))
a__f(s(0())) -> a__f(a__p(s(0())))
a__p(X) -> p(X)
a__p(s(0())) -> 0()
mark(0()) -> 0()
mark(cons(X1,X2)) -> cons(mark(X1),X2)
mark(f(X)) -> a__f(mark(X))
mark(p(X)) -> a__p(mark(X))
mark(s(X)) -> s(mark(X))
- Signature:
{a__f/1,a__p/1,mark/1} / {0/0,cons/2,f/1,p/1,s/1}
- Obligation:
innermost runtime complexity wrt. defined symbols {a__f,a__p,mark} and constructors {0,cons,f,p,s}
+ Applied Processor:
EmptyProcessor
+ Details:
The problem is already closed. The intended complexity is O(1).

WORST_CASE(?,O(n^1))
```