WORST_CASE(Omega(n^1), O(n^2))
proof of /export/starexec/sandbox2/benchmark/theBenchmark.xml
# AProVE Commit ID: 794c25de1cacf0d048858bcd21c9a779e1221865 marcel 20200619 unpublished dirty


The Derivational Complexity (innermost) of the given DCpxTrs could be proven to be BOUNDS(n^1, n^2).

(0) DCpxTrs
(1) DerivationalComplexityToRuntimeComplexityProof [BOTH BOUNDS(ID, ID), 0 ms]
(2) CpxRelTRS
(3) SInnermostTerminationProof [BOTH CONCRETE BOUNDS(ID, ID), 159 ms]
(4) CpxRelTRS
(5) RelTrsToWeightedTrsProof [BOTH BOUNDS(ID, ID), 0 ms]
(6) CpxWeightedTrs
    (7) CpxWeightedTrsRenamingProof [BOTH BOUNDS(ID, ID), 0 ms]
    (8) CpxWeightedTrs
    (9) TypeInferenceProof [BOTH BOUNDS(ID, ID), 0 ms]
    (10) CpxTypedWeightedTrs
    (11) CompletionProof [UPPER BOUND(ID), 0 ms]
    (12) CpxTypedWeightedCompleteTrs
    (13) CpxTypedWeightedTrsToRntsProof [UPPER BOUND(ID), 0 ms]
    (14) CpxRNTS
    (15) CompleteCoflocoProof [FINISHED, 421 ms]
    (16) BOUNDS(1, n^2)
(17) RenamingProof [BOTH BOUNDS(ID, ID), 0 ms]
(18) CpxRelTRS
    (19) TypeInferenceProof [BOTH BOUNDS(ID, ID), 0 ms]
    (20) typed CpxTrs
    (21) OrderProof [LOWER BOUND(ID), 0 ms]
    (22) typed CpxTrs
    (23) RewriteLemmaProof [LOWER BOUND(ID), 283 ms]
    (24) BEST
        (25) proven lower bound
            (26) LowerBoundPropagationProof [FINISHED, 0 ms]
            (27) BOUNDS(n^1, INF)
        (28) typed CpxTrs
            (29) RewriteLemmaProof [LOWER BOUND(ID), 53 ms]
            (30) BOUNDS(1, INF)


----------------------------------------

(0)
Obligation:
The Derivational Complexity (innermost) of the given DCpxTrs could be proven to be BOUNDS(n^1, n^2).


The TRS R consists of the following rules:

   +(0, y) -> y
   +(s(x), y) -> s(+(x, y))
   +(s(x), y) -> +(x, s(y))

S is empty.
Rewrite Strategy: INNERMOST
----------------------------------------

(1) DerivationalComplexityToRuntimeComplexityProof (BOTH BOUNDS(ID, ID))
The following rules have been added to S to convert the given derivational complexity problem to a runtime complexity problem:

   encArg(0) -> 0
   encArg(s(x_1)) -> s(encArg(x_1))
   encArg(cons_+(x_1, x_2)) -> +(encArg(x_1), encArg(x_2))
   encode_+(x_1, x_2) -> +(encArg(x_1), encArg(x_2))
   encode_0 -> 0
   encode_s(x_1) -> s(encArg(x_1))


----------------------------------------

(2)
Obligation:
The Runtime Complexity (innermost) of the given CpxRelTRS could be proven to be BOUNDS(n^1, n^2).


The TRS R consists of the following rules:

   +(0, y) -> y
   +(s(x), y) -> s(+(x, y))
   +(s(x), y) -> +(x, s(y))

The (relative) TRS S consists of the following rules:

   encArg(0) -> 0
   encArg(s(x_1)) -> s(encArg(x_1))
   encArg(cons_+(x_1, x_2)) -> +(encArg(x_1), encArg(x_2))
   encode_+(x_1, x_2) -> +(encArg(x_1), encArg(x_2))
   encode_0 -> 0
   encode_s(x_1) -> s(encArg(x_1))

Rewrite Strategy: INNERMOST
----------------------------------------

(3) SInnermostTerminationProof (BOTH CONCRETE BOUNDS(ID, ID))
proved innermost termination of relative rules
----------------------------------------

(4)
Obligation:
The Runtime Complexity (innermost) of the given CpxRelTRS could be proven to be BOUNDS(n^1, n^2).


The TRS R consists of the following rules:

   +(0, y) -> y
   +(s(x), y) -> s(+(x, y))
   +(s(x), y) -> +(x, s(y))

The (relative) TRS S consists of the following rules:

   encArg(0) -> 0
   encArg(s(x_1)) -> s(encArg(x_1))
   encArg(cons_+(x_1, x_2)) -> +(encArg(x_1), encArg(x_2))
   encode_+(x_1, x_2) -> +(encArg(x_1), encArg(x_2))
   encode_0 -> 0
   encode_s(x_1) -> s(encArg(x_1))

Rewrite Strategy: INNERMOST
----------------------------------------

(5) RelTrsToWeightedTrsProof (BOTH BOUNDS(ID, ID))
Transformed relative TRS to weighted TRS
----------------------------------------

(6)
Obligation:
The Runtime Complexity (innermost) of the given CpxWeightedTrs could be proven to be BOUNDS(1, n^2).


The TRS R consists of the following rules:

   +(0, y) -> y [1]
   +(s(x), y) -> s(+(x, y)) [1]
   +(s(x), y) -> +(x, s(y)) [1]
   encArg(0) -> 0 [0]
   encArg(s(x_1)) -> s(encArg(x_1)) [0]
   encArg(cons_+(x_1, x_2)) -> +(encArg(x_1), encArg(x_2)) [0]
   encode_+(x_1, x_2) -> +(encArg(x_1), encArg(x_2)) [0]
   encode_0 -> 0 [0]
   encode_s(x_1) -> s(encArg(x_1)) [0]

Rewrite Strategy: INNERMOST
----------------------------------------

(7) CpxWeightedTrsRenamingProof (BOTH BOUNDS(ID, ID))
Renamed defined symbols to avoid conflicts with arithmetic symbols:

+ => plus

----------------------------------------

(8)
Obligation:
The Runtime Complexity (innermost) of the given CpxWeightedTrs could be proven to be BOUNDS(1, n^2).


The TRS R consists of the following rules:

   plus(0, y) -> y [1]
   plus(s(x), y) -> s(plus(x, y)) [1]
   plus(s(x), y) -> plus(x, s(y)) [1]
   encArg(0) -> 0 [0]
   encArg(s(x_1)) -> s(encArg(x_1)) [0]
   encArg(cons_+(x_1, x_2)) -> plus(encArg(x_1), encArg(x_2)) [0]
   encode_+(x_1, x_2) -> plus(encArg(x_1), encArg(x_2)) [0]
   encode_0 -> 0 [0]
   encode_s(x_1) -> s(encArg(x_1)) [0]

Rewrite Strategy: INNERMOST
----------------------------------------

(9) TypeInferenceProof (BOTH BOUNDS(ID, ID))
Infered types.
----------------------------------------

(10)
Obligation:
Runtime Complexity Weighted TRS with Types.
The TRS R consists of the following rules:

   plus(0, y) -> y [1]
   plus(s(x), y) -> s(plus(x, y)) [1]
   plus(s(x), y) -> plus(x, s(y)) [1]
   encArg(0) -> 0 [0]
   encArg(s(x_1)) -> s(encArg(x_1)) [0]
   encArg(cons_+(x_1, x_2)) -> plus(encArg(x_1), encArg(x_2)) [0]
   encode_+(x_1, x_2) -> plus(encArg(x_1), encArg(x_2)) [0]
   encode_0 -> 0 [0]
   encode_s(x_1) -> s(encArg(x_1)) [0]

The TRS has the following type information:
plus :: 0:s:cons_+ -> 0:s:cons_+ -> 0:s:cons_+
0 :: 0:s:cons_+
s :: 0:s:cons_+ -> 0:s:cons_+
encArg :: 0:s:cons_+ -> 0:s:cons_+
cons_+ :: 0:s:cons_+ -> 0:s:cons_+ -> 0:s:cons_+
encode_+ :: 0:s:cons_+ -> 0:s:cons_+ -> 0:s:cons_+
encode_0 :: 0:s:cons_+
encode_s :: 0:s:cons_+ -> 0:s:cons_+

Rewrite Strategy: INNERMOST
----------------------------------------

(11) CompletionProof (UPPER BOUND(ID))
The TRS is a completely defined constructor system, as every type has a constant constructor and the following rules were added:

   encArg(v0) -> null_encArg [0]
   encode_+(v0, v1) -> null_encode_+ [0]
   encode_0 -> null_encode_0 [0]
   encode_s(v0) -> null_encode_s [0]
   plus(v0, v1) -> null_plus [0]

And the following fresh constants:    null_encArg, null_encode_+, null_encode_0, null_encode_s, null_plus

----------------------------------------

(12)
Obligation:
Runtime Complexity Weighted TRS where all functions are completely defined. The underlying TRS is:

Runtime Complexity Weighted TRS with Types.
The TRS R consists of the following rules:

   plus(0, y) -> y [1]
   plus(s(x), y) -> s(plus(x, y)) [1]
   plus(s(x), y) -> plus(x, s(y)) [1]
   encArg(0) -> 0 [0]
   encArg(s(x_1)) -> s(encArg(x_1)) [0]
   encArg(cons_+(x_1, x_2)) -> plus(encArg(x_1), encArg(x_2)) [0]
   encode_+(x_1, x_2) -> plus(encArg(x_1), encArg(x_2)) [0]
   encode_0 -> 0 [0]
   encode_s(x_1) -> s(encArg(x_1)) [0]
   encArg(v0) -> null_encArg [0]
   encode_+(v0, v1) -> null_encode_+ [0]
   encode_0 -> null_encode_0 [0]
   encode_s(v0) -> null_encode_s [0]
   plus(v0, v1) -> null_plus [0]

The TRS has the following type information:
plus :: 0:s:cons_+:null_encArg:null_encode_+:null_encode_0:null_encode_s:null_plus -> 0:s:cons_+:null_encArg:null_encode_+:null_encode_0:null_encode_s:null_plus -> 0:s:cons_+:null_encArg:null_encode_+:null_encode_0:null_encode_s:null_plus
0 :: 0:s:cons_+:null_encArg:null_encode_+:null_encode_0:null_encode_s:null_plus
s :: 0:s:cons_+:null_encArg:null_encode_+:null_encode_0:null_encode_s:null_plus -> 0:s:cons_+:null_encArg:null_encode_+:null_encode_0:null_encode_s:null_plus
encArg :: 0:s:cons_+:null_encArg:null_encode_+:null_encode_0:null_encode_s:null_plus -> 0:s:cons_+:null_encArg:null_encode_+:null_encode_0:null_encode_s:null_plus
cons_+ :: 0:s:cons_+:null_encArg:null_encode_+:null_encode_0:null_encode_s:null_plus -> 0:s:cons_+:null_encArg:null_encode_+:null_encode_0:null_encode_s:null_plus -> 0:s:cons_+:null_encArg:null_encode_+:null_encode_0:null_encode_s:null_plus
encode_+ :: 0:s:cons_+:null_encArg:null_encode_+:null_encode_0:null_encode_s:null_plus -> 0:s:cons_+:null_encArg:null_encode_+:null_encode_0:null_encode_s:null_plus -> 0:s:cons_+:null_encArg:null_encode_+:null_encode_0:null_encode_s:null_plus
encode_0 :: 0:s:cons_+:null_encArg:null_encode_+:null_encode_0:null_encode_s:null_plus
encode_s :: 0:s:cons_+:null_encArg:null_encode_+:null_encode_0:null_encode_s:null_plus -> 0:s:cons_+:null_encArg:null_encode_+:null_encode_0:null_encode_s:null_plus
null_encArg :: 0:s:cons_+:null_encArg:null_encode_+:null_encode_0:null_encode_s:null_plus
null_encode_+ :: 0:s:cons_+:null_encArg:null_encode_+:null_encode_0:null_encode_s:null_plus
null_encode_0 :: 0:s:cons_+:null_encArg:null_encode_+:null_encode_0:null_encode_s:null_plus
null_encode_s :: 0:s:cons_+:null_encArg:null_encode_+:null_encode_0:null_encode_s:null_plus
null_plus :: 0:s:cons_+:null_encArg:null_encode_+:null_encode_0:null_encode_s:null_plus

Rewrite Strategy: INNERMOST
----------------------------------------

(13) CpxTypedWeightedTrsToRntsProof (UPPER BOUND(ID))
Transformed the TRS into an over-approximating RNTS by (improved) Size Abstraction.
The constant constructors are abstracted as follows:

   0 => 0
   null_encArg => 0
   null_encode_+ => 0
   null_encode_0 => 0
   null_encode_s => 0
   null_plus => 0

----------------------------------------

(14)
Obligation:
Complexity RNTS consisting of the following rules:

   encArg(z) -{ 0 }-> plus(encArg(x_1), encArg(x_2)) :|: x_1 >= 0, z = 1 + x_1 + x_2, x_2 >= 0
   encArg(z) -{ 0 }-> 0 :|: z = 0
   encArg(z) -{ 0 }-> 0 :|: v0 >= 0, z = v0
   encArg(z) -{ 0 }-> 1 + encArg(x_1) :|: z = 1 + x_1, x_1 >= 0
   encode_+(z, z') -{ 0 }-> plus(encArg(x_1), encArg(x_2)) :|: x_1 >= 0, x_2 >= 0, z = x_1, z' = x_2
   encode_+(z, z') -{ 0 }-> 0 :|: v0 >= 0, v1 >= 0, z = v0, z' = v1
   encode_0 -{ 0 }-> 0 :|: 
   encode_s(z) -{ 0 }-> 0 :|: v0 >= 0, z = v0
   encode_s(z) -{ 0 }-> 1 + encArg(x_1) :|: x_1 >= 0, z = x_1
   plus(z, z') -{ 1 }-> y :|: y >= 0, z = 0, z' = y
   plus(z, z') -{ 1 }-> plus(x, 1 + y) :|: x >= 0, y >= 0, z = 1 + x, z' = y
   plus(z, z') -{ 0 }-> 0 :|: v0 >= 0, v1 >= 0, z = v0, z' = v1
   plus(z, z') -{ 1 }-> 1 + plus(x, y) :|: x >= 0, y >= 0, z = 1 + x, z' = y

Only complete derivations are relevant for the runtime complexity.

----------------------------------------

(15) CompleteCoflocoProof (FINISHED)
Transformed the RNTS (where only complete derivations are relevant) into cost relations for CoFloCo:

eq(start(V1, V),0,[plus(V1, V, Out)],[V1 >= 0,V >= 0]).
eq(start(V1, V),0,[encArg(V1, Out)],[V1 >= 0]).
eq(start(V1, V),0,[fun(V1, V, Out)],[V1 >= 0,V >= 0]).
eq(start(V1, V),0,[fun1(Out)],[]).
eq(start(V1, V),0,[fun2(V1, Out)],[V1 >= 0]).
eq(plus(V1, V, Out),1,[],[Out = V2,V2 >= 0,V1 = 0,V = V2]).
eq(plus(V1, V, Out),1,[plus(V3, V4, Ret1)],[Out = 1 + Ret1,V3 >= 0,V4 >= 0,V1 = 1 + V3,V = V4]).
eq(plus(V1, V, Out),1,[plus(V5, 1 + V6, Ret)],[Out = Ret,V5 >= 0,V6 >= 0,V1 = 1 + V5,V = V6]).
eq(encArg(V1, Out),0,[],[Out = 0,V1 = 0]).
eq(encArg(V1, Out),0,[encArg(V7, Ret11)],[Out = 1 + Ret11,V1 = 1 + V7,V7 >= 0]).
eq(encArg(V1, Out),0,[encArg(V8, Ret0),encArg(V9, Ret12),plus(Ret0, Ret12, Ret2)],[Out = Ret2,V8 >= 0,V1 = 1 + V8 + V9,V9 >= 0]).
eq(fun(V1, V, Out),0,[encArg(V10, Ret01),encArg(V11, Ret13),plus(Ret01, Ret13, Ret3)],[Out = Ret3,V10 >= 0,V11 >= 0,V1 = V10,V = V11]).
eq(fun1(Out),0,[],[Out = 0]).
eq(fun2(V1, Out),0,[encArg(V12, Ret14)],[Out = 1 + Ret14,V12 >= 0,V1 = V12]).
eq(encArg(V1, Out),0,[],[Out = 0,V13 >= 0,V1 = V13]).
eq(fun(V1, V, Out),0,[],[Out = 0,V15 >= 0,V14 >= 0,V1 = V15,V = V14]).
eq(fun2(V1, Out),0,[],[Out = 0,V16 >= 0,V1 = V16]).
eq(plus(V1, V, Out),0,[],[Out = 0,V17 >= 0,V18 >= 0,V1 = V17,V = V18]).
input_output_vars(plus(V1,V,Out),[V1,V],[Out]).
input_output_vars(encArg(V1,Out),[V1],[Out]).
input_output_vars(fun(V1,V,Out),[V1,V],[Out]).
input_output_vars(fun1(Out),[],[Out]).
input_output_vars(fun2(V1,Out),[V1],[Out]).


CoFloCo proof output:
Preprocessing Cost Relations
=====================================

#### Computed strongly connected components 
0. recursive  : [plus/3]
1. recursive [non_tail,multiple] : [encArg/2]
2. non_recursive  : [fun/3]
3. non_recursive  : [fun1/1]
4. non_recursive  : [fun2/2]
5. non_recursive  : [start/2]

#### Obtained direct recursion through partial evaluation 
0. SCC is partially evaluated into plus/3
1. SCC is partially evaluated into encArg/2
2. SCC is partially evaluated into fun/3
3. SCC is completely evaluated into other SCCs
4. SCC is partially evaluated into fun2/2
5. SCC is partially evaluated into start/2

Control-Flow Refinement of Cost Relations
=====================================

### Specialization of cost equations plus/3 
* CE 9 is refined into CE [17] 
* CE 6 is refined into CE [18] 
* CE 7 is refined into CE [19] 
* CE 8 is refined into CE [20] 


### Cost equations --> "Loop" of plus/3 
* CEs [19] --> Loop 11 
* CEs [20] --> Loop 12 
* CEs [17] --> Loop 13 
* CEs [18] --> Loop 14 

### Ranking functions of CR plus(V1,V,Out) 
* RF of phase [11,12]: [V1]

#### Partial ranking functions of CR plus(V1,V,Out) 
* Partial RF of phase [11,12]:
  - RF of loop [11:1,12:1]:
    V1


### Specialization of cost equations encArg/2 
* CE 10 is refined into CE [21] 
* CE 12 is refined into CE [22,23,24,25] 
* CE 11 is refined into CE [26] 


### Cost equations --> "Loop" of encArg/2 
* CEs [26] --> Loop 15 
* CEs [25] --> Loop 16 
* CEs [24] --> Loop 17 
* CEs [22] --> Loop 18 
* CEs [23] --> Loop 19 
* CEs [21] --> Loop 20 

### Ranking functions of CR encArg(V1,Out) 
* RF of phase [15,16,17,18,19]: [V1]

#### Partial ranking functions of CR encArg(V1,Out) 
* Partial RF of phase [15,16,17,18,19]:
  - RF of loop [15:1,16:1,16:2,17:1,17:2,18:1,18:2,19:1,19:2]:
    V1


### Specialization of cost equations fun/3 
* CE 13 is refined into CE [27,28,29,30,31,32,33,34,35,36,37,38] 
* CE 14 is refined into CE [39] 


### Cost equations --> "Loop" of fun/3 
* CEs [37] --> Loop 21 
* CEs [33,34,38] --> Loop 22 
* CEs [29,35] --> Loop 23 
* CEs [27,28,30,31,32,36,39] --> Loop 24 

### Ranking functions of CR fun(V1,V,Out) 

#### Partial ranking functions of CR fun(V1,V,Out) 


### Specialization of cost equations fun2/2 
* CE 15 is refined into CE [40,41] 
* CE 16 is refined into CE [42] 


### Cost equations --> "Loop" of fun2/2 
* CEs [41] --> Loop 25 
* CEs [40] --> Loop 26 
* CEs [42] --> Loop 27 

### Ranking functions of CR fun2(V1,Out) 

#### Partial ranking functions of CR fun2(V1,Out) 


### Specialization of cost equations start/2 
* CE 1 is refined into CE [43,44,45,46] 
* CE 2 is refined into CE [47,48] 
* CE 3 is refined into CE [49,50,51,52] 
* CE 4 is refined into CE [53] 
* CE 5 is refined into CE [54,55,56] 


### Cost equations --> "Loop" of start/2 
* CEs [43,44,45,46,47,48,49,50,51,52,53,54,55,56] --> Loop 28 

### Ranking functions of CR start(V1,V) 

#### Partial ranking functions of CR start(V1,V) 


Computing Bounds
=====================================

#### Cost of chains of plus(V1,V,Out):
* Chain [[11,12],14]: 2*it(11)+1
  Such that:aux(3) =< V1
it(11) =< aux(3)

  with precondition: [V+V1=Out,V1>=1,V>=0] 

* Chain [[11,12],13]: 2*it(11)+0
  Such that:aux(4) =< V1
it(11) =< aux(4)

  with precondition: [V1>=1,V>=0,Out>=0,V1>=Out] 

* Chain [14]: 1
  with precondition: [V1=0,V=Out,V>=0] 

* Chain [13]: 0
  with precondition: [Out=0,V1>=0,V>=0] 


#### Cost of chains of encArg(V1,Out):
* Chain [20]: 0
  with precondition: [Out=0,V1>=0] 

* Chain [multiple([15,16,17,18,19],[[20]])]: 1*it(17)+1*it(18)+2*s(9)+2*s(11)+0
  Such that:aux(11) =< V1
aux(12) =< 2/3*V1
it(15) =< aux(11)
it(17) =< aux(11)
it(18) =< aux(11)
it(17) =< aux(12)
aux(7) =< aux(11)
s(10) =< it(15)*aux(11)
s(12) =< it(17)*aux(7)
s(11) =< s(12)
s(9) =< s(10)

  with precondition: [V1>=1,Out>=0,V1>=Out] 


#### Cost of chains of fun(V1,V,Out):
* Chain [24]: 2*s(16)+2*s(17)+4*s(21)+4*s(22)+3*s(26)+3*s(27)+6*s(31)+6*s(32)+1
  Such that:aux(13) =< V1
aux(14) =< 2/3*V1
aux(15) =< V
aux(16) =< 2/3*V
s(26) =< aux(13)
s(27) =< aux(13)
s(26) =< aux(14)
s(28) =< aux(13)
s(29) =< aux(13)*aux(13)
s(30) =< s(26)*s(28)
s(31) =< s(30)
s(32) =< s(29)
s(16) =< aux(15)
s(17) =< aux(15)
s(16) =< aux(16)
s(18) =< aux(15)
s(19) =< aux(15)*aux(15)
s(20) =< s(16)*s(18)
s(21) =< s(20)
s(22) =< s(19)

  with precondition: [Out=0,V1>=0,V>=0] 

* Chain [23]: 2*s(66)+2*s(67)+4*s(71)+4*s(72)+1*s(76)+1*s(77)+2*s(81)+2*s(82)+1
  Such that:s(73) =< V1
s(74) =< 2/3*V1
aux(17) =< V
aux(18) =< 2/3*V
s(66) =< aux(17)
s(67) =< aux(17)
s(66) =< aux(18)
s(68) =< aux(17)
s(69) =< aux(17)*aux(17)
s(70) =< s(66)*s(68)
s(71) =< s(70)
s(72) =< s(69)
s(76) =< s(73)
s(77) =< s(73)
s(76) =< s(74)
s(78) =< s(73)
s(79) =< s(73)*s(73)
s(80) =< s(76)*s(78)
s(81) =< s(80)
s(82) =< s(79)

  with precondition: [V1>=0,V>=1,Out>=0,V>=Out] 

* Chain [22]: 3*s(96)+9*s(97)+6*s(101)+6*s(102)+1*s(130)+1*s(131)+2*s(135)+2*s(136)+1
  Such that:s(127) =< V
s(128) =< 2/3*V
aux(22) =< V1
aux(23) =< 2/3*V1
s(97) =< aux(22)
s(96) =< aux(22)
s(96) =< aux(23)
s(98) =< aux(22)
s(99) =< aux(22)*aux(22)
s(100) =< s(96)*s(98)
s(101) =< s(100)
s(102) =< s(99)
s(130) =< s(127)
s(131) =< s(127)
s(130) =< s(128)
s(132) =< s(127)
s(133) =< s(127)*s(127)
s(134) =< s(130)*s(132)
s(135) =< s(134)
s(136) =< s(133)

  with precondition: [V1>=1,V>=0,Out>=0,V1>=Out] 

* Chain [21]: 1*s(142)+3*s(143)+2*s(147)+2*s(148)+1*s(152)+1*s(153)+2*s(157)+2*s(158)+1
  Such that:s(140) =< 2/3*V1
s(149) =< V
s(150) =< 2/3*V
aux(24) =< V1
s(143) =< aux(24)
s(152) =< s(149)
s(153) =< s(149)
s(152) =< s(150)
s(154) =< s(149)
s(155) =< s(149)*s(149)
s(156) =< s(152)*s(154)
s(157) =< s(156)
s(158) =< s(155)
s(142) =< aux(24)
s(142) =< s(140)
s(144) =< aux(24)
s(145) =< aux(24)*aux(24)
s(146) =< s(142)*s(144)
s(147) =< s(146)
s(148) =< s(145)

  with precondition: [V1>=1,V>=1,Out>=1,V+V1>=Out] 


#### Cost of chains of fun2(V1,Out):
* Chain [27]: 0
  with precondition: [Out=0,V1>=0] 

* Chain [26]: 0
  with precondition: [Out=1,V1>=0] 

* Chain [25]: 1*s(164)+1*s(165)+2*s(169)+2*s(170)+0
  Such that:s(161) =< V1
s(162) =< 2/3*V1
s(164) =< s(161)
s(165) =< s(161)
s(164) =< s(162)
s(166) =< s(161)
s(167) =< s(161)*s(161)
s(168) =< s(164)*s(166)
s(169) =< s(168)
s(170) =< s(167)

  with precondition: [V1>=1,Out>=1,V1+1>=Out] 


#### Cost of chains of start(V1,V):
* Chain [28]: 22*s(172)+10*s(178)+20*s(183)+20*s(184)+6*s(196)+6*s(197)+12*s(201)+12*s(202)+1
  Such that:aux(25) =< V1
aux(26) =< 2/3*V1
aux(27) =< V
aux(28) =< 2/3*V
s(172) =< aux(25)
s(178) =< aux(25)
s(178) =< aux(26)
s(180) =< aux(25)
s(181) =< aux(25)*aux(25)
s(182) =< s(178)*s(180)
s(183) =< s(182)
s(184) =< s(181)
s(196) =< aux(27)
s(197) =< aux(27)
s(196) =< aux(28)
s(198) =< aux(27)
s(199) =< aux(27)*aux(27)
s(200) =< s(196)*s(198)
s(201) =< s(200)
s(202) =< s(199)

  with precondition: [] 


Closed-form bounds of start(V1,V): 
-------------------------------------
* Chain [28] with precondition: [] 
    - Upper bound: nat(V1)*32+1+nat(V1)*40*nat(V1)+nat(V)*12+nat(V)*24*nat(V) 
    - Complexity: n^2 

### Maximum cost of start(V1,V): nat(V1)*32+1+nat(V1)*40*nat(V1)+nat(V)*12+nat(V)*24*nat(V) 
Asymptotic class: n^2 
* Total analysis performed in 404 ms.


----------------------------------------

(16)
BOUNDS(1, n^2)

----------------------------------------

(17) RenamingProof (BOTH BOUNDS(ID, ID))
Renamed function symbols to avoid clashes with predefined symbol.
----------------------------------------

(18)
Obligation:
The Runtime Complexity (innermost) of the given CpxRelTRS could be proven to be BOUNDS(n^1, INF).


The TRS R consists of the following rules:

   +'(0', y) -> y
   +'(s(x), y) -> s(+'(x, y))
   +'(s(x), y) -> +'(x, s(y))

The (relative) TRS S consists of the following rules:

   encArg(0') -> 0'
   encArg(s(x_1)) -> s(encArg(x_1))
   encArg(cons_+(x_1, x_2)) -> +'(encArg(x_1), encArg(x_2))
   encode_+(x_1, x_2) -> +'(encArg(x_1), encArg(x_2))
   encode_0 -> 0'
   encode_s(x_1) -> s(encArg(x_1))

Rewrite Strategy: INNERMOST
----------------------------------------

(19) TypeInferenceProof (BOTH BOUNDS(ID, ID))
Infered types.
----------------------------------------

(20)
Obligation:
Innermost TRS:
Rules:
+'(0', y) -> y
+'(s(x), y) -> s(+'(x, y))
+'(s(x), y) -> +'(x, s(y))
encArg(0') -> 0'
encArg(s(x_1)) -> s(encArg(x_1))
encArg(cons_+(x_1, x_2)) -> +'(encArg(x_1), encArg(x_2))
encode_+(x_1, x_2) -> +'(encArg(x_1), encArg(x_2))
encode_0 -> 0'
encode_s(x_1) -> s(encArg(x_1))

Types:
+' :: 0':s:cons_+ -> 0':s:cons_+ -> 0':s:cons_+
0' :: 0':s:cons_+
s :: 0':s:cons_+ -> 0':s:cons_+
encArg :: 0':s:cons_+ -> 0':s:cons_+
cons_+ :: 0':s:cons_+ -> 0':s:cons_+ -> 0':s:cons_+
encode_+ :: 0':s:cons_+ -> 0':s:cons_+ -> 0':s:cons_+
encode_0 :: 0':s:cons_+
encode_s :: 0':s:cons_+ -> 0':s:cons_+
hole_0':s:cons_+1_3 :: 0':s:cons_+
gen_0':s:cons_+2_3 :: Nat -> 0':s:cons_+

----------------------------------------

(21) OrderProof (LOWER BOUND(ID))
Heuristically decided to analyse the following defined symbols:
+', encArg

They will be analysed ascendingly in the following order:
+' < encArg

----------------------------------------

(22)
Obligation:
Innermost TRS:
Rules:
+'(0', y) -> y
+'(s(x), y) -> s(+'(x, y))
+'(s(x), y) -> +'(x, s(y))
encArg(0') -> 0'
encArg(s(x_1)) -> s(encArg(x_1))
encArg(cons_+(x_1, x_2)) -> +'(encArg(x_1), encArg(x_2))
encode_+(x_1, x_2) -> +'(encArg(x_1), encArg(x_2))
encode_0 -> 0'
encode_s(x_1) -> s(encArg(x_1))

Types:
+' :: 0':s:cons_+ -> 0':s:cons_+ -> 0':s:cons_+
0' :: 0':s:cons_+
s :: 0':s:cons_+ -> 0':s:cons_+
encArg :: 0':s:cons_+ -> 0':s:cons_+
cons_+ :: 0':s:cons_+ -> 0':s:cons_+ -> 0':s:cons_+
encode_+ :: 0':s:cons_+ -> 0':s:cons_+ -> 0':s:cons_+
encode_0 :: 0':s:cons_+
encode_s :: 0':s:cons_+ -> 0':s:cons_+
hole_0':s:cons_+1_3 :: 0':s:cons_+
gen_0':s:cons_+2_3 :: Nat -> 0':s:cons_+


Generator Equations:
gen_0':s:cons_+2_3(0) <=> 0'
gen_0':s:cons_+2_3(+(x, 1)) <=> s(gen_0':s:cons_+2_3(x))


The following defined symbols remain to be analysed:
+', encArg

They will be analysed ascendingly in the following order:
+' < encArg

----------------------------------------

(23) RewriteLemmaProof (LOWER BOUND(ID))
Proved the following rewrite lemma:
+'(gen_0':s:cons_+2_3(n4_3), gen_0':s:cons_+2_3(b)) -> gen_0':s:cons_+2_3(+(n4_3, b)), rt in Omega(1 + n4_3)

Induction Base:
+'(gen_0':s:cons_+2_3(0), gen_0':s:cons_+2_3(b)) ->_R^Omega(1)
gen_0':s:cons_+2_3(b)

Induction Step:
+'(gen_0':s:cons_+2_3(+(n4_3, 1)), gen_0':s:cons_+2_3(b)) ->_R^Omega(1)
s(+'(gen_0':s:cons_+2_3(n4_3), gen_0':s:cons_+2_3(b))) ->_IH
s(gen_0':s:cons_+2_3(+(b, c5_3)))

We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n).
----------------------------------------

(24)
Complex Obligation (BEST)

----------------------------------------

(25)
Obligation:
Proved the lower bound n^1 for the following obligation:

Innermost TRS:
Rules:
+'(0', y) -> y
+'(s(x), y) -> s(+'(x, y))
+'(s(x), y) -> +'(x, s(y))
encArg(0') -> 0'
encArg(s(x_1)) -> s(encArg(x_1))
encArg(cons_+(x_1, x_2)) -> +'(encArg(x_1), encArg(x_2))
encode_+(x_1, x_2) -> +'(encArg(x_1), encArg(x_2))
encode_0 -> 0'
encode_s(x_1) -> s(encArg(x_1))

Types:
+' :: 0':s:cons_+ -> 0':s:cons_+ -> 0':s:cons_+
0' :: 0':s:cons_+
s :: 0':s:cons_+ -> 0':s:cons_+
encArg :: 0':s:cons_+ -> 0':s:cons_+
cons_+ :: 0':s:cons_+ -> 0':s:cons_+ -> 0':s:cons_+
encode_+ :: 0':s:cons_+ -> 0':s:cons_+ -> 0':s:cons_+
encode_0 :: 0':s:cons_+
encode_s :: 0':s:cons_+ -> 0':s:cons_+
hole_0':s:cons_+1_3 :: 0':s:cons_+
gen_0':s:cons_+2_3 :: Nat -> 0':s:cons_+


Generator Equations:
gen_0':s:cons_+2_3(0) <=> 0'
gen_0':s:cons_+2_3(+(x, 1)) <=> s(gen_0':s:cons_+2_3(x))


The following defined symbols remain to be analysed:
+', encArg

They will be analysed ascendingly in the following order:
+' < encArg

----------------------------------------

(26) LowerBoundPropagationProof (FINISHED)
Propagated lower bound.
----------------------------------------

(27)
BOUNDS(n^1, INF)

----------------------------------------

(28)
Obligation:
Innermost TRS:
Rules:
+'(0', y) -> y
+'(s(x), y) -> s(+'(x, y))
+'(s(x), y) -> +'(x, s(y))
encArg(0') -> 0'
encArg(s(x_1)) -> s(encArg(x_1))
encArg(cons_+(x_1, x_2)) -> +'(encArg(x_1), encArg(x_2))
encode_+(x_1, x_2) -> +'(encArg(x_1), encArg(x_2))
encode_0 -> 0'
encode_s(x_1) -> s(encArg(x_1))

Types:
+' :: 0':s:cons_+ -> 0':s:cons_+ -> 0':s:cons_+
0' :: 0':s:cons_+
s :: 0':s:cons_+ -> 0':s:cons_+
encArg :: 0':s:cons_+ -> 0':s:cons_+
cons_+ :: 0':s:cons_+ -> 0':s:cons_+ -> 0':s:cons_+
encode_+ :: 0':s:cons_+ -> 0':s:cons_+ -> 0':s:cons_+
encode_0 :: 0':s:cons_+
encode_s :: 0':s:cons_+ -> 0':s:cons_+
hole_0':s:cons_+1_3 :: 0':s:cons_+
gen_0':s:cons_+2_3 :: Nat -> 0':s:cons_+


Lemmas:
+'(gen_0':s:cons_+2_3(n4_3), gen_0':s:cons_+2_3(b)) -> gen_0':s:cons_+2_3(+(n4_3, b)), rt in Omega(1 + n4_3)


Generator Equations:
gen_0':s:cons_+2_3(0) <=> 0'
gen_0':s:cons_+2_3(+(x, 1)) <=> s(gen_0':s:cons_+2_3(x))


The following defined symbols remain to be analysed:
encArg
----------------------------------------

(29) RewriteLemmaProof (LOWER BOUND(ID))
Proved the following rewrite lemma:
encArg(gen_0':s:cons_+2_3(n877_3)) -> gen_0':s:cons_+2_3(n877_3), rt in Omega(0)

Induction Base:
encArg(gen_0':s:cons_+2_3(0)) ->_R^Omega(0)
0'

Induction Step:
encArg(gen_0':s:cons_+2_3(+(n877_3, 1))) ->_R^Omega(0)
s(encArg(gen_0':s:cons_+2_3(n877_3))) ->_IH
s(gen_0':s:cons_+2_3(c878_3))

We have rt in Omega(1) and sz in O(n). Thus, we have irc_R in Omega(n^0).
----------------------------------------

(30)
BOUNDS(1, INF)