/export/starexec/sandbox2/solver/bin/starexec_run_rcdcRelativeAlsoLower /export/starexec/sandbox2/benchmark/theBenchmark.xml /export/starexec/sandbox2/output/output_files


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


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), 165 ms]
(4) CpxRelTRS
(5) RelTrsToWeightedTrsProof [BOTH BOUNDS(ID, ID), 0 ms]
(6) CpxWeightedTrs
    (7) TypeInferenceProof [BOTH BOUNDS(ID, ID), 0 ms]
    (8) CpxTypedWeightedTrs
    (9) CompletionProof [UPPER BOUND(ID), 0 ms]
    (10) CpxTypedWeightedCompleteTrs
    (11) CpxTypedWeightedTrsToRntsProof [UPPER BOUND(ID), 0 ms]
    (12) CpxRNTS
    (13) CompleteCoflocoProof [FINISHED, 744 ms]
    (14) BOUNDS(1, n^2)
(15) RenamingProof [BOTH BOUNDS(ID, ID), 0 ms]
(16) CpxRelTRS
    (17) TypeInferenceProof [BOTH BOUNDS(ID, ID), 0 ms]
    (18) typed CpxTrs
    (19) OrderProof [LOWER BOUND(ID), 0 ms]
    (20) typed CpxTrs
    (21) RewriteLemmaProof [LOWER BOUND(ID), 497 ms]
    (22) BEST
        (23) proven lower bound
            (24) LowerBoundPropagationProof [FINISHED, 0 ms]
            (25) BOUNDS(n^1, INF)
        (26) typed CpxTrs
            (27) RewriteLemmaProof [LOWER BOUND(ID), 37 ms]
            (28) 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:

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

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(s(x_1)) -> s(encArg(x_1))
   encArg(0) -> 0
   encArg(cons_average(x_1, x_2)) -> average(encArg(x_1), encArg(x_2))
   encode_average(x_1, x_2) -> average(encArg(x_1), encArg(x_2))
   encode_s(x_1) -> s(encArg(x_1))
   encode_0 -> 0


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

(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:

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

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

   encArg(s(x_1)) -> s(encArg(x_1))
   encArg(0) -> 0
   encArg(cons_average(x_1, x_2)) -> average(encArg(x_1), encArg(x_2))
   encode_average(x_1, x_2) -> average(encArg(x_1), encArg(x_2))
   encode_s(x_1) -> s(encArg(x_1))
   encode_0 -> 0

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:

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

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

   encArg(s(x_1)) -> s(encArg(x_1))
   encArg(0) -> 0
   encArg(cons_average(x_1, x_2)) -> average(encArg(x_1), encArg(x_2))
   encode_average(x_1, x_2) -> average(encArg(x_1), encArg(x_2))
   encode_s(x_1) -> s(encArg(x_1))
   encode_0 -> 0

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:

   average(s(x), y) -> average(x, s(y)) [1]
   average(x, s(s(s(y)))) -> s(average(s(x), y)) [1]
   average(0, 0) -> 0 [1]
   average(0, s(0)) -> 0 [1]
   average(0, s(s(0))) -> s(0) [1]
   encArg(s(x_1)) -> s(encArg(x_1)) [0]
   encArg(0) -> 0 [0]
   encArg(cons_average(x_1, x_2)) -> average(encArg(x_1), encArg(x_2)) [0]
   encode_average(x_1, x_2) -> average(encArg(x_1), encArg(x_2)) [0]
   encode_s(x_1) -> s(encArg(x_1)) [0]
   encode_0 -> 0 [0]

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

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

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

   average(s(x), y) -> average(x, s(y)) [1]
   average(x, s(s(s(y)))) -> s(average(s(x), y)) [1]
   average(0, 0) -> 0 [1]
   average(0, s(0)) -> 0 [1]
   average(0, s(s(0))) -> s(0) [1]
   encArg(s(x_1)) -> s(encArg(x_1)) [0]
   encArg(0) -> 0 [0]
   encArg(cons_average(x_1, x_2)) -> average(encArg(x_1), encArg(x_2)) [0]
   encode_average(x_1, x_2) -> average(encArg(x_1), encArg(x_2)) [0]
   encode_s(x_1) -> s(encArg(x_1)) [0]
   encode_0 -> 0 [0]

The TRS has the following type information:
average :: s:0:cons_average -> s:0:cons_average -> s:0:cons_average
s :: s:0:cons_average -> s:0:cons_average
0 :: s:0:cons_average
encArg :: s:0:cons_average -> s:0:cons_average
cons_average :: s:0:cons_average -> s:0:cons_average -> s:0:cons_average
encode_average :: s:0:cons_average -> s:0:cons_average -> s:0:cons_average
encode_s :: s:0:cons_average -> s:0:cons_average
encode_0 :: s:0:cons_average

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

(9) 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_average(v0, v1) -> null_encode_average [0]
   encode_s(v0) -> null_encode_s [0]
   encode_0 -> null_encode_0 [0]
   average(v0, v1) -> null_average [0]

And the following fresh constants:    null_encArg, null_encode_average, null_encode_s, null_encode_0, null_average

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

(10)
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:

   average(s(x), y) -> average(x, s(y)) [1]
   average(x, s(s(s(y)))) -> s(average(s(x), y)) [1]
   average(0, 0) -> 0 [1]
   average(0, s(0)) -> 0 [1]
   average(0, s(s(0))) -> s(0) [1]
   encArg(s(x_1)) -> s(encArg(x_1)) [0]
   encArg(0) -> 0 [0]
   encArg(cons_average(x_1, x_2)) -> average(encArg(x_1), encArg(x_2)) [0]
   encode_average(x_1, x_2) -> average(encArg(x_1), encArg(x_2)) [0]
   encode_s(x_1) -> s(encArg(x_1)) [0]
   encode_0 -> 0 [0]
   encArg(v0) -> null_encArg [0]
   encode_average(v0, v1) -> null_encode_average [0]
   encode_s(v0) -> null_encode_s [0]
   encode_0 -> null_encode_0 [0]
   average(v0, v1) -> null_average [0]

The TRS has the following type information:
average :: s:0:cons_average:null_encArg:null_encode_average:null_encode_s:null_encode_0:null_average -> s:0:cons_average:null_encArg:null_encode_average:null_encode_s:null_encode_0:null_average -> s:0:cons_average:null_encArg:null_encode_average:null_encode_s:null_encode_0:null_average
s :: s:0:cons_average:null_encArg:null_encode_average:null_encode_s:null_encode_0:null_average -> s:0:cons_average:null_encArg:null_encode_average:null_encode_s:null_encode_0:null_average
0 :: s:0:cons_average:null_encArg:null_encode_average:null_encode_s:null_encode_0:null_average
encArg :: s:0:cons_average:null_encArg:null_encode_average:null_encode_s:null_encode_0:null_average -> s:0:cons_average:null_encArg:null_encode_average:null_encode_s:null_encode_0:null_average
cons_average :: s:0:cons_average:null_encArg:null_encode_average:null_encode_s:null_encode_0:null_average -> s:0:cons_average:null_encArg:null_encode_average:null_encode_s:null_encode_0:null_average -> s:0:cons_average:null_encArg:null_encode_average:null_encode_s:null_encode_0:null_average
encode_average :: s:0:cons_average:null_encArg:null_encode_average:null_encode_s:null_encode_0:null_average -> s:0:cons_average:null_encArg:null_encode_average:null_encode_s:null_encode_0:null_average -> s:0:cons_average:null_encArg:null_encode_average:null_encode_s:null_encode_0:null_average
encode_s :: s:0:cons_average:null_encArg:null_encode_average:null_encode_s:null_encode_0:null_average -> s:0:cons_average:null_encArg:null_encode_average:null_encode_s:null_encode_0:null_average
encode_0 :: s:0:cons_average:null_encArg:null_encode_average:null_encode_s:null_encode_0:null_average
null_encArg :: s:0:cons_average:null_encArg:null_encode_average:null_encode_s:null_encode_0:null_average
null_encode_average :: s:0:cons_average:null_encArg:null_encode_average:null_encode_s:null_encode_0:null_average
null_encode_s :: s:0:cons_average:null_encArg:null_encode_average:null_encode_s:null_encode_0:null_average
null_encode_0 :: s:0:cons_average:null_encArg:null_encode_average:null_encode_s:null_encode_0:null_average
null_average :: s:0:cons_average:null_encArg:null_encode_average:null_encode_s:null_encode_0:null_average

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

(11) 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_average => 0
   null_encode_s => 0
   null_encode_0 => 0
   null_average => 0

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

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

   average(z, z') -{ 1 }-> average(x, 1 + y) :|: x >= 0, y >= 0, z = 1 + x, z' = y
   average(z, z') -{ 1 }-> 0 :|: z = 0, z' = 0
   average(z, z') -{ 1 }-> 0 :|: z' = 1 + 0, z = 0
   average(z, z') -{ 0 }-> 0 :|: v0 >= 0, v1 >= 0, z = v0, z' = v1
   average(z, z') -{ 1 }-> 1 + average(1 + x, y) :|: x >= 0, y >= 0, z' = 1 + (1 + (1 + y)), z = x
   average(z, z') -{ 1 }-> 1 + 0 :|: z' = 1 + (1 + 0), z = 0
   encArg(z) -{ 0 }-> average(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_0 -{ 0 }-> 0 :|: 
   encode_average(z, z') -{ 0 }-> average(encArg(x_1), encArg(x_2)) :|: x_1 >= 0, x_2 >= 0, z = x_1, z' = x_2
   encode_average(z, z') -{ 0 }-> 0 :|: v0 >= 0, v1 >= 0, z = v0, z' = v1
   encode_s(z) -{ 0 }-> 0 :|: v0 >= 0, z = v0
   encode_s(z) -{ 0 }-> 1 + encArg(x_1) :|: x_1 >= 0, z = x_1

Only complete derivations are relevant for the runtime complexity.

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

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

eq(start(V1, V),0,[average(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(V1, Out)],[V1 >= 0]).
eq(start(V1, V),0,[fun2(Out)],[]).
eq(average(V1, V, Out),1,[average(V3, 1 + V2, Ret)],[Out = Ret,V3 >= 0,V2 >= 0,V1 = 1 + V3,V = V2]).
eq(average(V1, V, Out),1,[average(1 + V4, V5, Ret1)],[Out = 1 + Ret1,V4 >= 0,V5 >= 0,V = 3 + V5,V1 = V4]).
eq(average(V1, V, Out),1,[],[Out = 0,V1 = 0,V = 0]).
eq(average(V1, V, Out),1,[],[Out = 0,V = 1,V1 = 0]).
eq(average(V1, V, Out),1,[],[Out = 1,V = 2,V1 = 0]).
eq(encArg(V1, Out),0,[encArg(V6, Ret11)],[Out = 1 + Ret11,V1 = 1 + V6,V6 >= 0]).
eq(encArg(V1, Out),0,[],[Out = 0,V1 = 0]).
eq(encArg(V1, Out),0,[encArg(V7, Ret0),encArg(V8, Ret12),average(Ret0, Ret12, Ret2)],[Out = Ret2,V7 >= 0,V1 = 1 + V7 + V8,V8 >= 0]).
eq(fun(V1, V, Out),0,[encArg(V9, Ret01),encArg(V10, Ret13),average(Ret01, Ret13, Ret3)],[Out = Ret3,V9 >= 0,V10 >= 0,V1 = V9,V = V10]).
eq(fun1(V1, Out),0,[encArg(V11, Ret14)],[Out = 1 + Ret14,V11 >= 0,V1 = V11]).
eq(fun2(Out),0,[],[Out = 0]).
eq(encArg(V1, Out),0,[],[Out = 0,V12 >= 0,V1 = V12]).
eq(fun(V1, V, Out),0,[],[Out = 0,V14 >= 0,V13 >= 0,V1 = V14,V = V13]).
eq(fun1(V1, Out),0,[],[Out = 0,V15 >= 0,V1 = V15]).
eq(average(V1, V, Out),0,[],[Out = 0,V16 >= 0,V17 >= 0,V1 = V16,V = V17]).
input_output_vars(average(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(V1,Out),[V1],[Out]).
input_output_vars(fun2(Out),[],[Out]).


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

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

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

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

### Specialization of cost equations average/3 
* CE 10 is refined into CE [19] 
* CE 9 is refined into CE [20] 
* CE 8 is refined into CE [21] 
* CE 11 is refined into CE [22] 
* CE 7 is refined into CE [23] 
* CE 6 is refined into CE [24] 


### Cost equations --> "Loop" of average/3 
* CEs [23] --> Loop 12 
* CEs [24] --> Loop 13 
* CEs [19] --> Loop 14 
* CEs [20] --> Loop 15 
* CEs [21,22] --> Loop 16 

### Ranking functions of CR average(V1,V,Out) 
* RF of phase [12,13]: [2*V1+V-1]

#### Partial ranking functions of CR average(V1,V,Out) 
* Partial RF of phase [12,13]:
  - RF of loop [12:1]:
    V/3-2/3 depends on loops [13:1] 
  - RF of loop [13:1]:
    V1 depends on loops [12:1] 


### Specialization of cost equations encArg/2 
* CE 13 is refined into CE [25] 
* CE 14 is refined into CE [26,27,28,29] 
* CE 12 is refined into CE [30] 


### Cost equations --> "Loop" of encArg/2 
* CEs [30] --> Loop 17 
* CEs [29] --> Loop 18 
* CEs [28] --> Loop 19 
* CEs [27] --> Loop 20 
* CEs [26] --> Loop 21 
* CEs [25] --> Loop 22 

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

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


### Specialization of cost equations fun/3 
* CE 15 is refined into CE [31,32,33,34,35,36,37,38,39,40,41,42] 
* CE 16 is refined into CE [43] 


### Cost equations --> "Loop" of fun/3 
* CEs [37] --> Loop 23 
* CEs [38] --> Loop 24 
* CEs [41] --> Loop 25 
* CEs [42] --> Loop 26 
* CEs [34] --> Loop 27 
* CEs [35] --> Loop 28 
* CEs [33,40] --> Loop 29 
* CEs [31,32,36,39,43] --> Loop 30 

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

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


### Specialization of cost equations fun1/2 
* CE 17 is refined into CE [44,45] 
* CE 18 is refined into CE [46] 


### Cost equations --> "Loop" of fun1/2 
* CEs [45] --> Loop 31 
* CEs [44] --> Loop 32 
* CEs [46] --> Loop 33 

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

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


### Specialization of cost equations start/2 
* CE 1 is refined into CE [47,48,49,50] 
* CE 2 is refined into CE [51,52] 
* CE 3 is refined into CE [53,54,55,56,57,58,59,60] 
* CE 4 is refined into CE [61,62,63] 
* CE 5 is refined into CE [64] 


### Cost equations --> "Loop" of start/2 
* CEs [47,48,49,50,51,52,53,54,55,56,57,58,59,60,61,62,63,64] --> Loop 34 

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

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


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

#### Cost of chains of average(V1,V,Out):
* Chain [[12,13],16]: 2*it(12)+1
  Such that:aux(6) =< V1+2*Out
aux(5) =< 2*V1+V
it(12) =< aux(5)
it(12) =< aux(6)

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

* Chain [[12,13],15]: 2*it(12)+1
  Such that:aux(6) =< V1+2*Out
aux(5) =< V1+2*Out+1
it(12) =< aux(5)
it(12) =< aux(6)

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

* Chain [[12,13],14]: 2*it(12)+1
  Such that:aux(7) =< -V+4*Out
it(12) =< aux(7)

  with precondition: [V+V1=2*Out,V1>=0,V>=0,V+V1>=2,V+3*V1>=4] 

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

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

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


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

* Chain [multiple([17,18,19,20,21],[[22]])]: 2*it(18)+1*it(20)+1*it(21)+4*s(18)+2*s(20)+0
  Such that:aux(11) =< 2*V1
aux(17) =< V1
aux(18) =< V1/2
aux(19) =< 2/3*V1
it(18) =< aux(17)
it(20) =< aux(17)
it(21) =< aux(17)
it(20) =< aux(18)
it(18) =< aux(19)
it(20) =< aux(19)
aux(12) =< aux(11)-2
s(21) =< it(18)*aux(12)
s(19) =< it(18)*aux(11)
s(20) =< s(21)
s(18) =< s(19)

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


#### Cost of chains of fun(V1,V,Out):
* Chain [30]: 4*s(26)+2*s(27)+2*s(28)+4*s(32)+8*s(33)+4*s(38)+2*s(39)+2*s(40)+4*s(44)+8*s(45)+1
  Such that:aux(20) =< V1
aux(21) =< 2*V1
aux(22) =< V1/2
aux(23) =< 2/3*V1
aux(24) =< V
aux(25) =< 2*V
aux(26) =< V/2
aux(27) =< 2/3*V
s(38) =< aux(20)
s(39) =< aux(20)
s(40) =< aux(20)
s(39) =< aux(22)
s(38) =< aux(23)
s(39) =< aux(23)
s(41) =< aux(21)-2
s(42) =< s(38)*s(41)
s(43) =< s(38)*aux(21)
s(44) =< s(42)
s(45) =< s(43)
s(26) =< aux(24)
s(27) =< aux(24)
s(28) =< aux(24)
s(27) =< aux(26)
s(26) =< aux(27)
s(27) =< aux(27)
s(29) =< aux(25)-2
s(30) =< s(26)*s(29)
s(31) =< s(26)*aux(25)
s(32) =< s(30)
s(33) =< s(31)

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

* Chain [29]: 4*s(74)+2*s(75)+2*s(76)+4*s(80)+8*s(81)+2*s(86)+1*s(87)+1*s(88)+2*s(92)+4*s(93)+1
  Such that:s(83) =< V1
s(82) =< 2*V1
s(84) =< V1/2
s(85) =< 2/3*V1
aux(28) =< V
aux(29) =< 2*V
aux(30) =< V/2
aux(31) =< 2/3*V
s(74) =< aux(28)
s(75) =< aux(28)
s(76) =< aux(28)
s(75) =< aux(30)
s(74) =< aux(31)
s(75) =< aux(31)
s(77) =< aux(29)-2
s(78) =< s(74)*s(77)
s(79) =< s(74)*aux(29)
s(80) =< s(78)
s(81) =< s(79)
s(86) =< s(83)
s(87) =< s(83)
s(88) =< s(83)
s(87) =< s(84)
s(86) =< s(85)
s(87) =< s(85)
s(89) =< s(82)-2
s(90) =< s(86)*s(89)
s(91) =< s(86)*s(82)
s(92) =< s(90)
s(93) =< s(91)

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

* Chain [28]: 2*s(110)+1*s(111)+5*s(112)+2*s(116)+4*s(117)+1
  Such that:s(106) =< 2*V
s(108) =< V/2
s(109) =< 2/3*V
aux(32) =< V
s(112) =< aux(32)
s(110) =< aux(32)
s(111) =< aux(32)
s(111) =< s(108)
s(110) =< s(109)
s(111) =< s(109)
s(113) =< s(106)-2
s(114) =< s(110)*s(113)
s(115) =< s(110)*s(106)
s(116) =< s(114)
s(117) =< s(115)

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

* Chain [27]: 2*s(127)+1*s(128)+3*s(129)+2*s(133)+4*s(134)+1
  Such that:s(123) =< 2*V
s(125) =< V/2
s(126) =< 2/3*V
aux(33) =< V
s(129) =< aux(33)
s(127) =< aux(33)
s(128) =< aux(33)
s(128) =< s(125)
s(127) =< s(126)
s(128) =< s(126)
s(130) =< s(123)-2
s(131) =< s(127)*s(130)
s(132) =< s(127)*s(123)
s(133) =< s(131)
s(134) =< s(132)

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

* Chain [26]: 2*s(141)+1*s(142)+1*s(143)+2*s(147)+4*s(148)+2*s(153)+1*s(154)+1*s(155)+2*s(159)+4*s(160)+4*s(164)+1
  Such that:s(138) =< V1
s(137) =< 2*V1
s(139) =< V1/2
s(140) =< 2/3*V1
s(150) =< V
s(149) =< 2*V
s(151) =< V/2
s(152) =< 2/3*V
aux(34) =< 2*V1+V
s(164) =< aux(34)
s(153) =< s(150)
s(154) =< s(150)
s(155) =< s(150)
s(154) =< s(151)
s(153) =< s(152)
s(154) =< s(152)
s(156) =< s(149)-2
s(157) =< s(153)*s(156)
s(158) =< s(153)*s(149)
s(159) =< s(157)
s(160) =< s(158)
s(141) =< s(138)
s(142) =< s(138)
s(143) =< s(138)
s(142) =< s(139)
s(141) =< s(140)
s(142) =< s(140)
s(144) =< s(137)-2
s(145) =< s(141)*s(144)
s(146) =< s(141)*s(137)
s(147) =< s(145)
s(148) =< s(146)

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

* Chain [25]: 2*s(170)+1*s(171)+1*s(172)+2*s(176)+4*s(177)+2*s(182)+1*s(183)+1*s(184)+2*s(188)+4*s(189)+2*s(191)+1
  Such that:s(167) =< V1
s(166) =< 2*V1
s(190) =< 2*V1+V
s(168) =< V1/2
s(169) =< 2/3*V1
s(179) =< V
s(178) =< 2*V
s(180) =< V/2
s(181) =< 2/3*V
s(191) =< s(190)
s(182) =< s(179)
s(183) =< s(179)
s(184) =< s(179)
s(183) =< s(180)
s(182) =< s(181)
s(183) =< s(181)
s(185) =< s(178)-2
s(186) =< s(182)*s(185)
s(187) =< s(182)*s(178)
s(188) =< s(186)
s(189) =< s(187)
s(170) =< s(167)
s(171) =< s(167)
s(172) =< s(167)
s(171) =< s(168)
s(170) =< s(169)
s(171) =< s(169)
s(173) =< s(166)-2
s(174) =< s(170)*s(173)
s(175) =< s(170)*s(166)
s(176) =< s(174)
s(177) =< s(175)

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

* Chain [24]: 2*s(196)+1*s(197)+1*s(198)+2*s(202)+4*s(203)+4*s(207)+1
  Such that:s(193) =< V1
s(194) =< V1/2
s(195) =< 2/3*V1
aux(35) =< 2*V1
s(207) =< aux(35)
s(196) =< s(193)
s(197) =< s(193)
s(198) =< s(193)
s(197) =< s(194)
s(196) =< s(195)
s(197) =< s(195)
s(199) =< aux(35)-2
s(200) =< s(196)*s(199)
s(201) =< s(196)*aux(35)
s(202) =< s(200)
s(203) =< s(201)

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

* Chain [23]: 2*s(213)+1*s(214)+1*s(215)+2*s(219)+4*s(220)+2*s(222)+1
  Such that:s(210) =< V1
s(211) =< V1/2
s(212) =< 2/3*V1
aux(36) =< 2*V1
s(222) =< aux(36)
s(213) =< s(210)
s(214) =< s(210)
s(215) =< s(210)
s(214) =< s(211)
s(213) =< s(212)
s(214) =< s(212)
s(216) =< aux(36)-2
s(217) =< s(213)*s(216)
s(218) =< s(213)*aux(36)
s(219) =< s(217)
s(220) =< s(218)

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


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

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

* Chain [31]: 2*s(227)+1*s(228)+1*s(229)+2*s(233)+4*s(234)+0
  Such that:s(224) =< V1
s(223) =< 2*V1
s(225) =< V1/2
s(226) =< 2/3*V1
s(227) =< s(224)
s(228) =< s(224)
s(229) =< s(224)
s(228) =< s(225)
s(227) =< s(226)
s(228) =< s(226)
s(230) =< s(223)-2
s(231) =< s(227)*s(230)
s(232) =< s(227)*s(223)
s(233) =< s(231)
s(234) =< s(232)

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


#### Cost of chains of start(V1,V):
* Chain [34]: 12*s(236)+18*s(246)+9*s(247)+9*s(248)+18*s(252)+36*s(253)+16*s(270)+8*s(271)+14*s(272)+16*s(276)+32*s(277)+6*s(382)+1
  Such that:aux(38) =< V1
aux(39) =< 2*V1
aux(40) =< 2*V1+V
aux(41) =< V1/2
aux(42) =< 2/3*V1
aux(43) =< V
aux(44) =< 2*V
aux(45) =< V/2
aux(46) =< 2/3*V
s(246) =< aux(38)
s(247) =< aux(38)
s(248) =< aux(38)
s(247) =< aux(41)
s(246) =< aux(42)
s(247) =< aux(42)
s(249) =< aux(39)-2
s(250) =< s(246)*s(249)
s(251) =< s(246)*aux(39)
s(252) =< s(250)
s(253) =< s(251)
s(270) =< aux(43)
s(271) =< aux(43)
s(272) =< aux(43)
s(271) =< aux(45)
s(270) =< aux(46)
s(271) =< aux(46)
s(273) =< aux(44)-2
s(274) =< s(270)*s(273)
s(275) =< s(270)*aux(44)
s(276) =< s(274)
s(277) =< s(275)
s(236) =< aux(40)
s(382) =< aux(39)

  with precondition: [] 


Closed-form bounds of start(V1,V): 
-------------------------------------
* Chain [34] with precondition: [] 
    - Upper bound: nat(V1)*36+1+nat(V1)*18*nat(nat(2*V1)+ -2)+nat(V1)*36*nat(2*V1)+nat(V)*38+nat(V)*16*nat(nat(2*V)+ -2)+nat(V)*32*nat(2*V)+nat(2*V1)*6+nat(2*V1+V)*12 
    - Complexity: n^2 

### Maximum cost of start(V1,V): nat(V1)*36+1+nat(V1)*18*nat(nat(2*V1)+ -2)+nat(V1)*36*nat(2*V1)+nat(V)*38+nat(V)*16*nat(nat(2*V)+ -2)+nat(V)*32*nat(2*V)+nat(2*V1)*6+nat(2*V1+V)*12 
Asymptotic class: n^2 
* Total analysis performed in 598 ms.


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

(14)
BOUNDS(1, n^2)

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

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

(16)
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:

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

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

   encArg(s(x_1)) -> s(encArg(x_1))
   encArg(0') -> 0'
   encArg(cons_average(x_1, x_2)) -> average(encArg(x_1), encArg(x_2))
   encode_average(x_1, x_2) -> average(encArg(x_1), encArg(x_2))
   encode_s(x_1) -> s(encArg(x_1))
   encode_0 -> 0'

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

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

(18)
Obligation:
Innermost TRS:
Rules:
average(s(x), y) -> average(x, s(y))
average(x, s(s(s(y)))) -> s(average(s(x), y))
average(0', 0') -> 0'
average(0', s(0')) -> 0'
average(0', s(s(0'))) -> s(0')
encArg(s(x_1)) -> s(encArg(x_1))
encArg(0') -> 0'
encArg(cons_average(x_1, x_2)) -> average(encArg(x_1), encArg(x_2))
encode_average(x_1, x_2) -> average(encArg(x_1), encArg(x_2))
encode_s(x_1) -> s(encArg(x_1))
encode_0 -> 0'

Types:
average :: s:0':cons_average -> s:0':cons_average -> s:0':cons_average
s :: s:0':cons_average -> s:0':cons_average
0' :: s:0':cons_average
encArg :: s:0':cons_average -> s:0':cons_average
cons_average :: s:0':cons_average -> s:0':cons_average -> s:0':cons_average
encode_average :: s:0':cons_average -> s:0':cons_average -> s:0':cons_average
encode_s :: s:0':cons_average -> s:0':cons_average
encode_0 :: s:0':cons_average
hole_s:0':cons_average1_3 :: s:0':cons_average
gen_s:0':cons_average2_3 :: Nat -> s:0':cons_average

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

(19) OrderProof (LOWER BOUND(ID))
Heuristically decided to analyse the following defined symbols:
average, encArg

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

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

(20)
Obligation:
Innermost TRS:
Rules:
average(s(x), y) -> average(x, s(y))
average(x, s(s(s(y)))) -> s(average(s(x), y))
average(0', 0') -> 0'
average(0', s(0')) -> 0'
average(0', s(s(0'))) -> s(0')
encArg(s(x_1)) -> s(encArg(x_1))
encArg(0') -> 0'
encArg(cons_average(x_1, x_2)) -> average(encArg(x_1), encArg(x_2))
encode_average(x_1, x_2) -> average(encArg(x_1), encArg(x_2))
encode_s(x_1) -> s(encArg(x_1))
encode_0 -> 0'

Types:
average :: s:0':cons_average -> s:0':cons_average -> s:0':cons_average
s :: s:0':cons_average -> s:0':cons_average
0' :: s:0':cons_average
encArg :: s:0':cons_average -> s:0':cons_average
cons_average :: s:0':cons_average -> s:0':cons_average -> s:0':cons_average
encode_average :: s:0':cons_average -> s:0':cons_average -> s:0':cons_average
encode_s :: s:0':cons_average -> s:0':cons_average
encode_0 :: s:0':cons_average
hole_s:0':cons_average1_3 :: s:0':cons_average
gen_s:0':cons_average2_3 :: Nat -> s:0':cons_average


Generator Equations:
gen_s:0':cons_average2_3(0) <=> 0'
gen_s:0':cons_average2_3(+(x, 1)) <=> s(gen_s:0':cons_average2_3(x))


The following defined symbols remain to be analysed:
average, encArg

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

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

(21) RewriteLemmaProof (LOWER BOUND(ID))
Proved the following rewrite lemma:
average(gen_s:0':cons_average2_3(+(1, n4_3)), gen_s:0':cons_average2_3(b)) -> *3_3, rt in Omega(n4_3)

Induction Base:
average(gen_s:0':cons_average2_3(+(1, 0)), gen_s:0':cons_average2_3(b))

Induction Step:
average(gen_s:0':cons_average2_3(+(1, +(n4_3, 1))), gen_s:0':cons_average2_3(b)) ->_R^Omega(1)
average(gen_s:0':cons_average2_3(+(1, n4_3)), s(gen_s:0':cons_average2_3(b))) ->_IH
*3_3

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

(22)
Complex Obligation (BEST)

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

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

Innermost TRS:
Rules:
average(s(x), y) -> average(x, s(y))
average(x, s(s(s(y)))) -> s(average(s(x), y))
average(0', 0') -> 0'
average(0', s(0')) -> 0'
average(0', s(s(0'))) -> s(0')
encArg(s(x_1)) -> s(encArg(x_1))
encArg(0') -> 0'
encArg(cons_average(x_1, x_2)) -> average(encArg(x_1), encArg(x_2))
encode_average(x_1, x_2) -> average(encArg(x_1), encArg(x_2))
encode_s(x_1) -> s(encArg(x_1))
encode_0 -> 0'

Types:
average :: s:0':cons_average -> s:0':cons_average -> s:0':cons_average
s :: s:0':cons_average -> s:0':cons_average
0' :: s:0':cons_average
encArg :: s:0':cons_average -> s:0':cons_average
cons_average :: s:0':cons_average -> s:0':cons_average -> s:0':cons_average
encode_average :: s:0':cons_average -> s:0':cons_average -> s:0':cons_average
encode_s :: s:0':cons_average -> s:0':cons_average
encode_0 :: s:0':cons_average
hole_s:0':cons_average1_3 :: s:0':cons_average
gen_s:0':cons_average2_3 :: Nat -> s:0':cons_average


Generator Equations:
gen_s:0':cons_average2_3(0) <=> 0'
gen_s:0':cons_average2_3(+(x, 1)) <=> s(gen_s:0':cons_average2_3(x))


The following defined symbols remain to be analysed:
average, encArg

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

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

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

(25)
BOUNDS(n^1, INF)

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

(26)
Obligation:
Innermost TRS:
Rules:
average(s(x), y) -> average(x, s(y))
average(x, s(s(s(y)))) -> s(average(s(x), y))
average(0', 0') -> 0'
average(0', s(0')) -> 0'
average(0', s(s(0'))) -> s(0')
encArg(s(x_1)) -> s(encArg(x_1))
encArg(0') -> 0'
encArg(cons_average(x_1, x_2)) -> average(encArg(x_1), encArg(x_2))
encode_average(x_1, x_2) -> average(encArg(x_1), encArg(x_2))
encode_s(x_1) -> s(encArg(x_1))
encode_0 -> 0'

Types:
average :: s:0':cons_average -> s:0':cons_average -> s:0':cons_average
s :: s:0':cons_average -> s:0':cons_average
0' :: s:0':cons_average
encArg :: s:0':cons_average -> s:0':cons_average
cons_average :: s:0':cons_average -> s:0':cons_average -> s:0':cons_average
encode_average :: s:0':cons_average -> s:0':cons_average -> s:0':cons_average
encode_s :: s:0':cons_average -> s:0':cons_average
encode_0 :: s:0':cons_average
hole_s:0':cons_average1_3 :: s:0':cons_average
gen_s:0':cons_average2_3 :: Nat -> s:0':cons_average


Lemmas:
average(gen_s:0':cons_average2_3(+(1, n4_3)), gen_s:0':cons_average2_3(b)) -> *3_3, rt in Omega(n4_3)


Generator Equations:
gen_s:0':cons_average2_3(0) <=> 0'
gen_s:0':cons_average2_3(+(x, 1)) <=> s(gen_s:0':cons_average2_3(x))


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

(27) RewriteLemmaProof (LOWER BOUND(ID))
Proved the following rewrite lemma:
encArg(gen_s:0':cons_average2_3(n632_3)) -> gen_s:0':cons_average2_3(n632_3), rt in Omega(0)

Induction Base:
encArg(gen_s:0':cons_average2_3(0)) ->_R^Omega(0)
0'

Induction Step:
encArg(gen_s:0':cons_average2_3(+(n632_3, 1))) ->_R^Omega(0)
s(encArg(gen_s:0':cons_average2_3(n632_3))) ->_IH
s(gen_s:0':cons_average2_3(c633_3))

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

(28)
BOUNDS(1, INF)