WORST_CASE(Omega(n^1),O(n^1))
* Step 1: Sum WORST_CASE(Omega(n^1),O(n^1))
+ Considered Problem:
- Strict TRS:
comp_f_g#1(comp_f_g(x7,x9),walk_xs_3(x8),x12) -> comp_f_g#1(x7,x9,Cons(x8,x12))
comp_f_g#1(walk_xs(),walk_xs_3(x8),x12) -> Cons(x8,x12)
main(Cons(x4,x5)) -> comp_f_g#1(walk#1(x5),walk_xs_3(x4),Nil())
main(Nil()) -> Nil()
walk#1(Cons(x4,x3)) -> comp_f_g(walk#1(x3),walk_xs_3(x4))
walk#1(Nil()) -> walk_xs()
- Signature:
{comp_f_g#1/3,main/1,walk#1/1} / {Cons/2,Nil/0,comp_f_g/2,walk_xs/0,walk_xs_3/1}
- Obligation:
innermost runtime complexity wrt. defined symbols {comp_f_g#1,main,walk#1} and constructors {Cons,Nil
,comp_f_g,walk_xs,walk_xs_3}
+ Applied Processor:
Sum {left = someStrategy, right = someStrategy}
+ Details:
()
** Step 1.a:1: DecreasingLoops WORST_CASE(Omega(n^1),?)
+ Considered Problem:
- Strict TRS:
comp_f_g#1(comp_f_g(x7,x9),walk_xs_3(x8),x12) -> comp_f_g#1(x7,x9,Cons(x8,x12))
comp_f_g#1(walk_xs(),walk_xs_3(x8),x12) -> Cons(x8,x12)
main(Cons(x4,x5)) -> comp_f_g#1(walk#1(x5),walk_xs_3(x4),Nil())
main(Nil()) -> Nil()
walk#1(Cons(x4,x3)) -> comp_f_g(walk#1(x3),walk_xs_3(x4))
walk#1(Nil()) -> walk_xs()
- Signature:
{comp_f_g#1/3,main/1,walk#1/1} / {Cons/2,Nil/0,comp_f_g/2,walk_xs/0,walk_xs_3/1}
- Obligation:
innermost runtime complexity wrt. defined symbols {comp_f_g#1,main,walk#1} and constructors {Cons,Nil
,comp_f_g,walk_xs,walk_xs_3}
+ Applied Processor:
DecreasingLoops {bound = AnyLoop, narrow = 10}
+ Details:
The system has following decreasing Loops:
walk#1(y){y -> Cons(x,y)} =
walk#1(Cons(x,y)) ->^+ comp_f_g(walk#1(y),walk_xs_3(x))
= C[walk#1(y) = walk#1(y){}]
** Step 1.b:1: NaturalPI WORST_CASE(?,O(n^1))
+ Considered Problem:
- Strict TRS:
comp_f_g#1(comp_f_g(x7,x9),walk_xs_3(x8),x12) -> comp_f_g#1(x7,x9,Cons(x8,x12))
comp_f_g#1(walk_xs(),walk_xs_3(x8),x12) -> Cons(x8,x12)
main(Cons(x4,x5)) -> comp_f_g#1(walk#1(x5),walk_xs_3(x4),Nil())
main(Nil()) -> Nil()
walk#1(Cons(x4,x3)) -> comp_f_g(walk#1(x3),walk_xs_3(x4))
walk#1(Nil()) -> walk_xs()
- Signature:
{comp_f_g#1/3,main/1,walk#1/1} / {Cons/2,Nil/0,comp_f_g/2,walk_xs/0,walk_xs_3/1}
- Obligation:
innermost runtime complexity wrt. defined symbols {comp_f_g#1,main,walk#1} and constructors {Cons,Nil
,comp_f_g,walk_xs,walk_xs_3}
+ Applied Processor:
NaturalPI {shape = Linear, restrict = Restrict, uargs = UArgs, urules = URules, selector = Just any strict-rules}
+ Details:
We apply a polynomial interpretation of kind constructor-based(linear):
The following argument positions are considered usable:
uargs(comp_f_g) = {1},
uargs(comp_f_g#1) = {1}
Following symbols are considered usable:
{comp_f_g#1,main,walk#1}
TcT has computed the following interpretation:
p(Cons) = 11
p(Nil) = 3
p(comp_f_g) = x1
p(comp_f_g#1) = 11 + 2*x1
p(main) = 11
p(walk#1) = 0
p(walk_xs) = 0
p(walk_xs_3) = 1
Following rules are strictly oriented:
main(Nil()) = 11
> 3
= Nil()
Following rules are (at-least) weakly oriented:
comp_f_g#1(comp_f_g(x7,x9),walk_xs_3(x8),x12) = 11 + 2*x7
>= 11 + 2*x7
= comp_f_g#1(x7,x9,Cons(x8,x12))
comp_f_g#1(walk_xs(),walk_xs_3(x8),x12) = 11
>= 11
= Cons(x8,x12)
main(Cons(x4,x5)) = 11
>= 11
= comp_f_g#1(walk#1(x5),walk_xs_3(x4),Nil())
walk#1(Cons(x4,x3)) = 0
>= 0
= comp_f_g(walk#1(x3),walk_xs_3(x4))
walk#1(Nil()) = 0
>= 0
= walk_xs()
** Step 1.b:2: NaturalPI WORST_CASE(?,O(n^1))
+ Considered Problem:
- Strict TRS:
comp_f_g#1(comp_f_g(x7,x9),walk_xs_3(x8),x12) -> comp_f_g#1(x7,x9,Cons(x8,x12))
comp_f_g#1(walk_xs(),walk_xs_3(x8),x12) -> Cons(x8,x12)
main(Cons(x4,x5)) -> comp_f_g#1(walk#1(x5),walk_xs_3(x4),Nil())
walk#1(Cons(x4,x3)) -> comp_f_g(walk#1(x3),walk_xs_3(x4))
walk#1(Nil()) -> walk_xs()
- Weak TRS:
main(Nil()) -> Nil()
- Signature:
{comp_f_g#1/3,main/1,walk#1/1} / {Cons/2,Nil/0,comp_f_g/2,walk_xs/0,walk_xs_3/1}
- Obligation:
innermost runtime complexity wrt. defined symbols {comp_f_g#1,main,walk#1} and constructors {Cons,Nil
,comp_f_g,walk_xs,walk_xs_3}
+ Applied Processor:
NaturalPI {shape = Linear, restrict = Restrict, uargs = UArgs, urules = URules, selector = Just any strict-rules}
+ Details:
We apply a polynomial interpretation of kind constructor-based(linear):
The following argument positions are considered usable:
uargs(comp_f_g) = {1},
uargs(comp_f_g#1) = {1}
Following symbols are considered usable:
{comp_f_g#1,main,walk#1}
TcT has computed the following interpretation:
p(Cons) = 4
p(Nil) = 12
p(comp_f_g) = x1
p(comp_f_g#1) = 2 + x1
p(main) = 12
p(walk#1) = 2
p(walk_xs) = 2
p(walk_xs_3) = 1
Following rules are strictly oriented:
main(Cons(x4,x5)) = 12
> 4
= comp_f_g#1(walk#1(x5),walk_xs_3(x4),Nil())
Following rules are (at-least) weakly oriented:
comp_f_g#1(comp_f_g(x7,x9),walk_xs_3(x8),x12) = 2 + x7
>= 2 + x7
= comp_f_g#1(x7,x9,Cons(x8,x12))
comp_f_g#1(walk_xs(),walk_xs_3(x8),x12) = 4
>= 4
= Cons(x8,x12)
main(Nil()) = 12
>= 12
= Nil()
walk#1(Cons(x4,x3)) = 2
>= 2
= comp_f_g(walk#1(x3),walk_xs_3(x4))
walk#1(Nil()) = 2
>= 2
= walk_xs()
** Step 1.b:3: NaturalPI WORST_CASE(?,O(n^1))
+ Considered Problem:
- Strict TRS:
comp_f_g#1(comp_f_g(x7,x9),walk_xs_3(x8),x12) -> comp_f_g#1(x7,x9,Cons(x8,x12))
comp_f_g#1(walk_xs(),walk_xs_3(x8),x12) -> Cons(x8,x12)
walk#1(Cons(x4,x3)) -> comp_f_g(walk#1(x3),walk_xs_3(x4))
walk#1(Nil()) -> walk_xs()
- Weak TRS:
main(Cons(x4,x5)) -> comp_f_g#1(walk#1(x5),walk_xs_3(x4),Nil())
main(Nil()) -> Nil()
- Signature:
{comp_f_g#1/3,main/1,walk#1/1} / {Cons/2,Nil/0,comp_f_g/2,walk_xs/0,walk_xs_3/1}
- Obligation:
innermost runtime complexity wrt. defined symbols {comp_f_g#1,main,walk#1} and constructors {Cons,Nil
,comp_f_g,walk_xs,walk_xs_3}
+ Applied Processor:
NaturalPI {shape = Linear, restrict = Restrict, uargs = UArgs, urules = URules, selector = Just any strict-rules}
+ Details:
We apply a polynomial interpretation of kind constructor-based(linear):
The following argument positions are considered usable:
uargs(comp_f_g) = {1},
uargs(comp_f_g#1) = {1}
Following symbols are considered usable:
{comp_f_g#1,main,walk#1}
TcT has computed the following interpretation:
p(Cons) = 2
p(Nil) = 10
p(comp_f_g) = x1
p(comp_f_g#1) = x1
p(main) = 10
p(walk#1) = 10
p(walk_xs) = 10
p(walk_xs_3) = 0
Following rules are strictly oriented:
comp_f_g#1(walk_xs(),walk_xs_3(x8),x12) = 10
> 2
= Cons(x8,x12)
Following rules are (at-least) weakly oriented:
comp_f_g#1(comp_f_g(x7,x9),walk_xs_3(x8),x12) = x7
>= x7
= comp_f_g#1(x7,x9,Cons(x8,x12))
main(Cons(x4,x5)) = 10
>= 10
= comp_f_g#1(walk#1(x5),walk_xs_3(x4),Nil())
main(Nil()) = 10
>= 10
= Nil()
walk#1(Cons(x4,x3)) = 10
>= 10
= comp_f_g(walk#1(x3),walk_xs_3(x4))
walk#1(Nil()) = 10
>= 10
= walk_xs()
** Step 1.b:4: NaturalPI WORST_CASE(?,O(n^1))
+ Considered Problem:
- Strict TRS:
comp_f_g#1(comp_f_g(x7,x9),walk_xs_3(x8),x12) -> comp_f_g#1(x7,x9,Cons(x8,x12))
walk#1(Cons(x4,x3)) -> comp_f_g(walk#1(x3),walk_xs_3(x4))
walk#1(Nil()) -> walk_xs()
- Weak TRS:
comp_f_g#1(walk_xs(),walk_xs_3(x8),x12) -> Cons(x8,x12)
main(Cons(x4,x5)) -> comp_f_g#1(walk#1(x5),walk_xs_3(x4),Nil())
main(Nil()) -> Nil()
- Signature:
{comp_f_g#1/3,main/1,walk#1/1} / {Cons/2,Nil/0,comp_f_g/2,walk_xs/0,walk_xs_3/1}
- Obligation:
innermost runtime complexity wrt. defined symbols {comp_f_g#1,main,walk#1} and constructors {Cons,Nil
,comp_f_g,walk_xs,walk_xs_3}
+ Applied Processor:
NaturalPI {shape = Linear, restrict = Restrict, uargs = UArgs, urules = URules, selector = Just any strict-rules}
+ Details:
We apply a polynomial interpretation of kind constructor-based(linear):
The following argument positions are considered usable:
uargs(comp_f_g) = {1},
uargs(comp_f_g#1) = {1}
Following symbols are considered usable:
{comp_f_g#1,main,walk#1}
TcT has computed the following interpretation:
p(Cons) = 0
p(Nil) = 14
p(comp_f_g) = x1
p(comp_f_g#1) = 5 + 8*x1
p(main) = 14
p(walk#1) = 1
p(walk_xs) = 0
p(walk_xs_3) = 1 + x1
Following rules are strictly oriented:
walk#1(Nil()) = 1
> 0
= walk_xs()
Following rules are (at-least) weakly oriented:
comp_f_g#1(comp_f_g(x7,x9),walk_xs_3(x8),x12) = 5 + 8*x7
>= 5 + 8*x7
= comp_f_g#1(x7,x9,Cons(x8,x12))
comp_f_g#1(walk_xs(),walk_xs_3(x8),x12) = 5
>= 0
= Cons(x8,x12)
main(Cons(x4,x5)) = 14
>= 13
= comp_f_g#1(walk#1(x5),walk_xs_3(x4),Nil())
main(Nil()) = 14
>= 14
= Nil()
walk#1(Cons(x4,x3)) = 1
>= 1
= comp_f_g(walk#1(x3),walk_xs_3(x4))
** Step 1.b:5: NaturalPI WORST_CASE(?,O(n^1))
+ Considered Problem:
- Strict TRS:
comp_f_g#1(comp_f_g(x7,x9),walk_xs_3(x8),x12) -> comp_f_g#1(x7,x9,Cons(x8,x12))
walk#1(Cons(x4,x3)) -> comp_f_g(walk#1(x3),walk_xs_3(x4))
- Weak TRS:
comp_f_g#1(walk_xs(),walk_xs_3(x8),x12) -> Cons(x8,x12)
main(Cons(x4,x5)) -> comp_f_g#1(walk#1(x5),walk_xs_3(x4),Nil())
main(Nil()) -> Nil()
walk#1(Nil()) -> walk_xs()
- Signature:
{comp_f_g#1/3,main/1,walk#1/1} / {Cons/2,Nil/0,comp_f_g/2,walk_xs/0,walk_xs_3/1}
- Obligation:
innermost runtime complexity wrt. defined symbols {comp_f_g#1,main,walk#1} and constructors {Cons,Nil
,comp_f_g,walk_xs,walk_xs_3}
+ Applied Processor:
NaturalPI {shape = Linear, restrict = Restrict, uargs = UArgs, urules = URules, selector = Just any strict-rules}
+ Details:
We apply a polynomial interpretation of kind constructor-based(linear):
The following argument positions are considered usable:
uargs(comp_f_g) = {1},
uargs(comp_f_g#1) = {1}
Following symbols are considered usable:
{comp_f_g#1,main,walk#1}
TcT has computed the following interpretation:
p(Cons) = 4 + x2
p(Nil) = 2
p(comp_f_g) = 1 + x1
p(comp_f_g#1) = 5*x1 + x3
p(main) = 2 + 5*x1
p(walk#1) = x1
p(walk_xs) = 1
p(walk_xs_3) = x1
Following rules are strictly oriented:
comp_f_g#1(comp_f_g(x7,x9),walk_xs_3(x8),x12) = 5 + x12 + 5*x7
> 4 + x12 + 5*x7
= comp_f_g#1(x7,x9,Cons(x8,x12))
walk#1(Cons(x4,x3)) = 4 + x3
> 1 + x3
= comp_f_g(walk#1(x3),walk_xs_3(x4))
Following rules are (at-least) weakly oriented:
comp_f_g#1(walk_xs(),walk_xs_3(x8),x12) = 5 + x12
>= 4 + x12
= Cons(x8,x12)
main(Cons(x4,x5)) = 22 + 5*x5
>= 2 + 5*x5
= comp_f_g#1(walk#1(x5),walk_xs_3(x4),Nil())
main(Nil()) = 12
>= 2
= Nil()
walk#1(Nil()) = 2
>= 1
= walk_xs()
** Step 1.b:6: EmptyProcessor WORST_CASE(?,O(1))
+ Considered Problem:
- Weak TRS:
comp_f_g#1(comp_f_g(x7,x9),walk_xs_3(x8),x12) -> comp_f_g#1(x7,x9,Cons(x8,x12))
comp_f_g#1(walk_xs(),walk_xs_3(x8),x12) -> Cons(x8,x12)
main(Cons(x4,x5)) -> comp_f_g#1(walk#1(x5),walk_xs_3(x4),Nil())
main(Nil()) -> Nil()
walk#1(Cons(x4,x3)) -> comp_f_g(walk#1(x3),walk_xs_3(x4))
walk#1(Nil()) -> walk_xs()
- Signature:
{comp_f_g#1/3,main/1,walk#1/1} / {Cons/2,Nil/0,comp_f_g/2,walk_xs/0,walk_xs_3/1}
- Obligation:
innermost runtime complexity wrt. defined symbols {comp_f_g#1,main,walk#1} and constructors {Cons,Nil
,comp_f_g,walk_xs,walk_xs_3}
+ Applied Processor:
EmptyProcessor
+ Details:
The problem is already closed. The intended complexity is O(1).
WORST_CASE(Omega(n^1),O(n^1))