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


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


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


The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(1, n^2).

(0) CpxTRS
(1) DependencyGraphProof [UPPER BOUND(ID), 0 ms]
(2) CpxTRS
(3) NonCtorToCtorProof [UPPER BOUND(ID), 0 ms]
(4) CpxRelTRS
(5) RcToIrcProof [BOTH BOUNDS(ID, ID), 0 ms]
(6) CpxRelTRS
(7) RelTrsToWeightedTrsProof [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, 745 ms]
(16) BOUNDS(1, n^2)


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

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


The TRS R consists of the following rules:

   f(j(x, y), y) -> g(f(x, k(y)))
   f(x, h1(y, z)) -> h2(0, x, h1(y, z))
   g(h2(x, y, h1(z, u))) -> h2(s(x), y, h1(z, u))
   h2(x, j(y, h1(z, u)), h1(z, u)) -> h2(s(x), y, h1(s(z), u))
   i(f(x, h(y))) -> y
   i(h2(s(x), y, h1(x, z))) -> z
   k(h(x)) -> h1(0, x)
   k(h1(x, y)) -> h1(s(x), y)

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

(1) DependencyGraphProof (UPPER BOUND(ID))
The following rules are not reachable from basic terms in the dependency graph and can be removed:

i(f(x, h(y))) -> y
i(h2(s(x), y, h1(x, z))) -> z

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

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


The TRS R consists of the following rules:

   f(j(x, y), y) -> g(f(x, k(y)))
   f(x, h1(y, z)) -> h2(0, x, h1(y, z))
   g(h2(x, y, h1(z, u))) -> h2(s(x), y, h1(z, u))
   h2(x, j(y, h1(z, u)), h1(z, u)) -> h2(s(x), y, h1(s(z), u))
   k(h(x)) -> h1(0, x)
   k(h1(x, y)) -> h1(s(x), y)

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

(3) NonCtorToCtorProof (UPPER BOUND(ID))
transformed non-ctor to ctor-system
----------------------------------------

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


The TRS R consists of the following rules:

   f(j(x, y), y) -> g(f(x, k(y)))
   f(x, h1(y, z)) -> h2(0, x, h1(y, z))
   h2(x, j(y, h1(z, u)), h1(z, u)) -> h2(s(x), y, h1(s(z), u))
   k(h(x)) -> h1(0, x)
   k(h1(x, y)) -> h1(s(x), y)
   g(c_h2(x, y, h1(z, u))) -> h2(s(x), y, h1(z, u))

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

   h2(x0, x1, x2) -> c_h2(x0, x1, x2)

Rewrite Strategy: FULL
----------------------------------------

(5) RcToIrcProof (BOTH BOUNDS(ID, ID))
Converted rc-obligation to irc-obligation.

As the TRS is a non-duplicating overlay system, we have rc = irc.
----------------------------------------

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


The TRS R consists of the following rules:

   f(j(x, y), y) -> g(f(x, k(y)))
   f(x, h1(y, z)) -> h2(0, x, h1(y, z))
   h2(x, j(y, h1(z, u)), h1(z, u)) -> h2(s(x), y, h1(s(z), u))
   k(h(x)) -> h1(0, x)
   k(h1(x, y)) -> h1(s(x), y)
   g(c_h2(x, y, h1(z, u))) -> h2(s(x), y, h1(z, u))

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

   h2(x0, x1, x2) -> c_h2(x0, x1, x2)

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

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

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

   f(j(x, y), y) -> g(f(x, k(y))) [1]
   f(x, h1(y, z)) -> h2(0, x, h1(y, z)) [1]
   h2(x, j(y, h1(z, u)), h1(z, u)) -> h2(s(x), y, h1(s(z), u)) [1]
   k(h(x)) -> h1(0, x) [1]
   k(h1(x, y)) -> h1(s(x), y) [1]
   g(c_h2(x, y, h1(z, u))) -> h2(s(x), y, h1(z, u)) [1]
   h2(x0, x1, x2) -> c_h2(x0, x1, x2) [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:

   f(j(x, y), y) -> g(f(x, k(y))) [1]
   f(x, h1(y, z)) -> h2(0, x, h1(y, z)) [1]
   h2(x, j(y, h1(z, u)), h1(z, u)) -> h2(s(x), y, h1(s(z), u)) [1]
   k(h(x)) -> h1(0, x) [1]
   k(h1(x, y)) -> h1(s(x), y) [1]
   g(c_h2(x, y, h1(z, u))) -> h2(s(x), y, h1(z, u)) [1]
   h2(x0, x1, x2) -> c_h2(x0, x1, x2) [0]

The TRS has the following type information:
f :: j -> h1:h -> c_h2
j :: j -> h1:h -> j
g :: c_h2 -> c_h2
k :: h1:h -> h1:h
h1 :: 0:s -> a -> h1:h
h2 :: 0:s -> j -> h1:h -> c_h2
0 :: 0:s
s :: 0:s -> 0:s
h :: a -> h1:h
c_h2 :: 0:s -> j -> h1:h -> c_h2

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:

   h2(v0, v1, v2) -> null_h2 [0]
   f(v0, v1) -> null_f [0]
   k(v0) -> null_k [0]
   g(v0) -> null_g [0]

And the following fresh constants:    null_h2, null_f, null_k, null_g, const, const1

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

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

   f(j(x, y), y) -> g(f(x, k(y))) [1]
   f(x, h1(y, z)) -> h2(0, x, h1(y, z)) [1]
   h2(x, j(y, h1(z, u)), h1(z, u)) -> h2(s(x), y, h1(s(z), u)) [1]
   k(h(x)) -> h1(0, x) [1]
   k(h1(x, y)) -> h1(s(x), y) [1]
   g(c_h2(x, y, h1(z, u))) -> h2(s(x), y, h1(z, u)) [1]
   h2(x0, x1, x2) -> c_h2(x0, x1, x2) [0]
   h2(v0, v1, v2) -> null_h2 [0]
   f(v0, v1) -> null_f [0]
   k(v0) -> null_k [0]
   g(v0) -> null_g [0]

The TRS has the following type information:
f :: j -> h1:h:null_k -> c_h2:null_h2:null_f:null_g
j :: j -> h1:h:null_k -> j
g :: c_h2:null_h2:null_f:null_g -> c_h2:null_h2:null_f:null_g
k :: h1:h:null_k -> h1:h:null_k
h1 :: 0:s -> a -> h1:h:null_k
h2 :: 0:s -> j -> h1:h:null_k -> c_h2:null_h2:null_f:null_g
0 :: 0:s
s :: 0:s -> 0:s
h :: a -> h1:h:null_k
c_h2 :: 0:s -> j -> h1:h:null_k -> c_h2:null_h2:null_f:null_g
null_h2 :: c_h2:null_h2:null_f:null_g
null_f :: c_h2:null_h2:null_f:null_g
null_k :: h1:h:null_k
null_g :: c_h2:null_h2:null_f:null_g
const :: j
const1 :: a

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_h2 => 0
   null_f => 0
   null_k => 0
   null_g => 0
   const => 0
   const1 => 0

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

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

   f(z', z'') -{ 1 }-> h2(0, x, 1 + y + z) :|: z >= 0, z' = x, x >= 0, y >= 0, z'' = 1 + y + z
   f(z', z'') -{ 1 }-> g(f(x, k(y))) :|: z'' = y, z' = 1 + x + y, x >= 0, y >= 0
   f(z', z'') -{ 0 }-> 0 :|: v0 >= 0, v1 >= 0, z'' = v1, z' = v0
   g(z') -{ 1 }-> h2(1 + x, y, 1 + z + u) :|: z >= 0, x >= 0, y >= 0, z' = 1 + x + y + (1 + z + u), u >= 0
   g(z') -{ 0 }-> 0 :|: v0 >= 0, z' = v0
   h2(z', z'', z1) -{ 1 }-> h2(1 + x, y, 1 + (1 + z) + u) :|: z >= 0, z' = x, x >= 0, y >= 0, z1 = 1 + z + u, z'' = 1 + y + (1 + z + u), u >= 0
   h2(z', z'', z1) -{ 0 }-> 0 :|: v0 >= 0, z1 = v2, v1 >= 0, z'' = v1, v2 >= 0, z' = v0
   h2(z', z'', z1) -{ 0 }-> 1 + x0 + x1 + x2 :|: z'' = x1, x0 >= 0, x1 >= 0, z1 = x2, x2 >= 0, z' = x0
   k(z') -{ 0 }-> 0 :|: v0 >= 0, z' = v0
   k(z') -{ 1 }-> 1 + 0 + x :|: z' = 1 + x, x >= 0
   k(z') -{ 1 }-> 1 + (1 + x) + y :|: z' = 1 + x + y, x >= 0, y >= 0

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(V, V2, V11),0,[f(V, V2, Out)],[V >= 0,V2 >= 0]).
eq(start(V, V2, V11),0,[h2(V, V2, V11, Out)],[V >= 0,V2 >= 0,V11 >= 0]).
eq(start(V, V2, V11),0,[k(V, Out)],[V >= 0]).
eq(start(V, V2, V11),0,[g(V, Out)],[V >= 0]).
eq(f(V, V2, Out),1,[k(V3, Ret01),f(V1, Ret01, Ret0),g(Ret0, Ret)],[Out = Ret,V2 = V3,V = 1 + V1 + V3,V1 >= 0,V3 >= 0]).
eq(f(V, V2, Out),1,[h2(0, V4, 1 + V6 + V5, Ret1)],[Out = Ret1,V5 >= 0,V = V4,V4 >= 0,V6 >= 0,V2 = 1 + V5 + V6]).
eq(h2(V, V2, V11, Out),1,[h2(1 + V8, V9, 1 + (1 + V10) + V7, Ret2)],[Out = Ret2,V10 >= 0,V = V8,V8 >= 0,V9 >= 0,V11 = 1 + V10 + V7,V2 = 2 + V10 + V7 + V9,V7 >= 0]).
eq(k(V, Out),1,[],[Out = 1 + V12,V = 1 + V12,V12 >= 0]).
eq(k(V, Out),1,[],[Out = 2 + V13 + V14,V = 1 + V13 + V14,V14 >= 0,V13 >= 0]).
eq(g(V, Out),1,[h2(1 + V18, V15, 1 + V17 + V16, Ret3)],[Out = Ret3,V17 >= 0,V18 >= 0,V15 >= 0,V = 2 + V15 + V16 + V17 + V18,V16 >= 0]).
eq(h2(V, V2, V11, Out),0,[],[Out = 1 + V19 + V20 + V21,V2 = V20,V21 >= 0,V20 >= 0,V11 = V19,V19 >= 0,V = V21]).
eq(h2(V, V2, V11, Out),0,[],[Out = 0,V23 >= 0,V11 = V24,V22 >= 0,V2 = V22,V24 >= 0,V = V23]).
eq(f(V, V2, Out),0,[],[Out = 0,V26 >= 0,V25 >= 0,V2 = V25,V = V26]).
eq(k(V, Out),0,[],[Out = 0,V27 >= 0,V = V27]).
eq(g(V, Out),0,[],[Out = 0,V28 >= 0,V = V28]).
input_output_vars(f(V,V2,Out),[V,V2],[Out]).
input_output_vars(h2(V,V2,V11,Out),[V,V2,V11],[Out]).
input_output_vars(k(V,Out),[V],[Out]).
input_output_vars(g(V,Out),[V],[Out]).


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

#### Computed strongly connected components 
0. recursive  : [h2/4]
1. non_recursive  : [g/2]
2. non_recursive  : [k/2]
3. recursive [non_tail] : [f/3]
4. non_recursive  : [start/3]

#### Obtained direct recursion through partial evaluation 
0. SCC is partially evaluated into h2/4
1. SCC is partially evaluated into g/2
2. SCC is partially evaluated into k/2
3. SCC is partially evaluated into f/3
4. SCC is partially evaluated into start/3

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

### Specialization of cost equations h2/4 
* CE 9 is refined into CE [16] 
* CE 10 is refined into CE [17] 
* CE 8 is refined into CE [18] 


### Cost equations --> "Loop" of h2/4 
* CEs [18] --> Loop 13 
* CEs [16] --> Loop 14 
* CEs [17] --> Loop 15 

### Ranking functions of CR h2(V,V2,V11,Out) 
* RF of phase [13]: [V2/2-1/2,V2/3-V11/3]

#### Partial ranking functions of CR h2(V,V2,V11,Out) 
* Partial RF of phase [13]:
  - RF of loop [13:1]:
    V2/2-1/2
    V2/3-V11/3


### Specialization of cost equations g/2 
* CE 14 is refined into CE [19,20,21] 
* CE 15 is refined into CE [22] 


### Cost equations --> "Loop" of g/2 
* CEs [21] --> Loop 16 
* CEs [20] --> Loop 17 
* CEs [19,22] --> Loop 18 

### Ranking functions of CR g(V,Out) 

#### Partial ranking functions of CR g(V,Out) 


### Specialization of cost equations k/2 
* CE 11 is refined into CE [23] 
* CE 12 is refined into CE [24] 
* CE 13 is refined into CE [25] 


### Cost equations --> "Loop" of k/2 
* CEs [23] --> Loop 19 
* CEs [24] --> Loop 20 
* CEs [25] --> Loop 21 

### Ranking functions of CR k(V,Out) 

#### Partial ranking functions of CR k(V,Out) 


### Specialization of cost equations f/3 
* CE 6 is refined into CE [26,27,28] 
* CE 7 is refined into CE [29] 
* CE 5 is refined into CE [30,31,32,33,34,35,36,37,38] 


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

### Ranking functions of CR f(V,V2,Out) 
* RF of phase [22,23,24,25]: [V/2-1/2,V/2-V2/2]
* RF of phase [26,27]: [V,V-V2]
* RF of phase [28,29]: [V/2-1/2,V/2-V2/2]
* RF of phase [30]: [V,V-V2]

#### Partial ranking functions of CR f(V,V2,Out) 
* Partial RF of phase [22,23,24,25]:
  - RF of loop [22:1,23:1]:
    V/2-V2/2
  - RF of loop [22:1,23:1,24:1,25:1]:
    V/2-1/2
  - RF of loop [24:1,25:1]:
    V/3-V2/3
* Partial RF of phase [26,27]:
  - RF of loop [26:1,27:1]:
    V
    V-V2
* Partial RF of phase [28,29]:
  - RF of loop [28:1]:
    V/2-V2/2
  - RF of loop [28:1,29:1]:
    V/2-1/2
  - RF of loop [29:1]:
    V/3-V2/3
* Partial RF of phase [30]:
  - RF of loop [30:1]:
    V
    V-V2


### Specialization of cost equations start/3 
* CE 1 is refined into CE [39,40,41] 
* CE 2 is refined into CE [42,43,44] 
* CE 3 is refined into CE [45,46,47] 
* CE 4 is refined into CE [48,49,50] 


### Cost equations --> "Loop" of start/3 
* CEs [39,40,41,42,43,44,45,46,47,48,49,50] --> Loop 34 

### Ranking functions of CR start(V,V2,V11) 

#### Partial ranking functions of CR start(V,V2,V11) 


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

#### Cost of chains of h2(V,V2,V11,Out):
* Chain [[13],15]: 1*it(13)+0
  Such that:it(13) =< V2/3-V11/3

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

* Chain [[13],14]: 1*it(13)+0
  Such that:it(13) =< V2/3-V11/3

  with precondition: [V>=0,V11>=1,Out>=V+V11+3,V+V2+2>=Out] 

* Chain [15]: 0
  with precondition: [Out=0,V>=0,V2>=0,V11>=0] 

* Chain [14]: 0
  with precondition: [V+V2+V11+1=Out,V>=0,V2>=0,V11>=0] 


#### Cost of chains of g(V,Out):
* Chain [18]: 1*s(2)+1
  Such that:s(2) =< V/3

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

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

* Chain [16]: 1*s(3)+1
  Such that:s(3) =< V/3

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


#### Cost of chains of k(V,Out):
* Chain [21]: 0
  with precondition: [Out=0,V>=0] 

* Chain [20]: 1
  with precondition: [V+1=Out,V>=1] 

* Chain [19]: 1
  with precondition: [V=Out,V>=1] 


#### Cost of chains of f(V,V2,Out):
* Chain [[30],33]: 3*it(30)+1
  Such that:aux(1) =< V-V2
it(30) =< aux(1)

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

* Chain [[28,29],[30],33]: 6*it(28)+3*it(30)+1*s(10)+1*s(11)+1
  Such that:aux(4) =< V/2
aux(5) =< V/2-V2/2
aux(2) =< V/3
aux(8) =< V-V2
it(28) =< aux(8)
it(30) =< aux(8)
it(28) =< aux(4)
it(28) =< aux(5)
aux(3) =< aux(2)+1/3
s(10) =< it(28)*aux(2)
s(11) =< it(28)*aux(3)

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

* Chain [[28,29],[22,23,24,25],32]: 6*it(22)+6*it(24)+6*it(28)+1*s(10)+1*s(11)+1*s(16)+1*s(17)+1
  Such that:aux(9) =< V
aux(6) =< 2*V-V2/2+1
aux(16) =< 4*V-V2+2
aux(5) =< V/2-V2/2
aux(2) =< V/3
aux(18) =< V-V2
aux(19) =< V/2
aux(20) =< 4/3*V-V2/3+2/3
it(28) =< aux(20)
it(22) =< aux(19)
it(24) =< aux(19)
it(22) =< aux(18)
it(24) =< aux(18)
it(22) =< aux(20)
it(24) =< aux(20)
it(24) =< aux(16)
aux(10) =< aux(9)+1/3
s(16) =< it(22)*aux(9)
s(17) =< it(24)*aux(10)
it(28) =< aux(19)
it(28) =< aux(5)
it(28) =< aux(6)
aux(3) =< aux(2)+1/3
s(10) =< it(28)*aux(2)
s(11) =< it(28)*aux(3)

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

* Chain [[28,29],[22,23,24,25],31]: 9*it(22)+9*it(24)+1*s(10)+1*s(11)+1*s(16)+1*s(17)+1*s(18)+1
  Such that:aux(9) =< V
aux(2) =< V/3
aux(23) =< V-V2
aux(24) =< V/2
aux(25) =< V/2-V2/2
aux(26) =< V/3-V2/3
it(24) =< aux(26)
s(18) =< aux(26)
it(22) =< aux(24)
it(24) =< aux(24)
it(22) =< aux(25)
it(24) =< aux(25)
it(22) =< aux(23)
it(24) =< aux(23)
aux(10) =< aux(9)+1/3
s(16) =< it(22)*aux(9)
s(17) =< it(24)*aux(10)
aux(3) =< aux(2)+1/3
s(10) =< it(22)*aux(2)
s(11) =< it(24)*aux(3)

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

* Chain [[28,29],33]: 3*it(28)+3*it(29)+1*s(4)+1*s(10)+1*s(11)+1
  Such that:aux(5) =< V/2-V2/2
aux(2) =< V/3
s(4) =< V/3-2/3*V2
it(29) =< V/3-V2/3
aux(6) =< 2/3*V-V2/6+1/3
aux(27) =< V/2
it(28) =< aux(27)
it(29) =< aux(27)
it(28) =< aux(5)
it(29) =< aux(5)
it(28) =< aux(6)
it(29) =< aux(6)
aux(3) =< aux(2)+1/3
s(10) =< it(28)*aux(2)
s(11) =< it(29)*aux(3)

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

* Chain [[28,29],32]: 3*it(28)+3*it(29)+1*s(10)+1*s(11)+1
  Such that:aux(5) =< V/2-V2/2
aux(2) =< V/3
it(29) =< V/3-V2/3
aux(6) =< 2/3*V-V2/6+1/3
aux(28) =< V/2
it(28) =< aux(28)
it(29) =< aux(28)
it(28) =< aux(5)
it(29) =< aux(5)
it(28) =< aux(6)
it(29) =< aux(6)
aux(3) =< aux(2)+1/3
s(10) =< it(28)*aux(2)
s(11) =< it(29)*aux(3)

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

* Chain [[28,29],31]: 3*it(28)+3*it(29)+1*s(10)+1*s(11)+1*s(18)+1
  Such that:aux(4) =< V/2
aux(5) =< V/2-V2/2
aux(2) =< V/3
it(29) =< V/3-V2/3
aux(29) =< V-V2
s(18) =< aux(29)
it(28) =< aux(4)
it(29) =< aux(4)
it(28) =< aux(5)
it(29) =< aux(5)
it(28) =< aux(29)
it(29) =< aux(29)
aux(3) =< aux(2)+1/3
s(10) =< it(28)*aux(2)
s(11) =< it(29)*aux(3)

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

* Chain [[22,23,24,25],32]: 6*it(22)+6*it(24)+1*s(16)+1*s(17)+1
  Such that:aux(12) =< V/2-V2/2
aux(9) =< V/3
aux(15) =< V/3-V2/3
aux(13) =< 2/3*V-V2/6+1/3
aux(16) =< 4/9*V-V2/9+2/9
aux(17) =< V/2
it(22) =< aux(17)
it(24) =< aux(17)
it(22) =< aux(12)
it(24) =< aux(12)
it(22) =< aux(13)
it(24) =< aux(13)
it(24) =< aux(15)
it(24) =< aux(16)
aux(10) =< aux(9)+1/3
s(16) =< it(22)*aux(9)
s(17) =< it(24)*aux(10)

  with precondition: [V2>=1,Out>=3,V>=V2+1,V+2>=Out] 

* Chain [[22,23,24,25],31]: 6*it(22)+6*it(24)+1*s(16)+1*s(17)+1*s(18)+1
  Such that:aux(11) =< V/2
aux(12) =< V/2-V2/2
aux(9) =< V/3
aux(21) =< V-V2
aux(22) =< V/3-V2/3
s(18) =< aux(22)
it(22) =< aux(11)
it(24) =< aux(11)
it(22) =< aux(12)
it(24) =< aux(12)
it(22) =< aux(21)
it(24) =< aux(21)
it(24) =< aux(22)
aux(10) =< aux(9)+1/3
s(16) =< it(22)*aux(9)
s(17) =< it(24)*aux(10)

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

* Chain [33]: 1*s(4)+1
  Such that:s(4) =< V/3-V2/3

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

* Chain [32]: 1
  with precondition: [V+V2+1=Out,V>=0,V2>=1] 

* Chain [31]: 1*s(18)+1
  Such that:s(18) =< V/3-V2/3

  with precondition: [V2>=1,Out>=V2+3,V+2>=Out] 


#### Cost of chains of start(V,V2,V11):
* Chain [34]: 1*s(117)+4*s(126)+18*s(127)+6*s(128)+24*s(129)+1*s(131)+1*s(132)+4*s(134)+3*s(135)+6*s(136)+6*s(137)+6*s(138)+1*s(139)+1*s(140)+1*s(141)+1*s(142)+7*s(143)+1*s(144)+12*s(145)+3*s(146)+2*s(147)+6*s(162)+1*s(164)+2*s(165)+2*s(167)+1
  Such that:s(119) =< V
s(115) =< 2*V-V2/2+1
s(116) =< 4*V-V2+2
s(117) =< V/3-2/3*V2
s(118) =< 4/3*V-V2/3+2/3
s(150) =< 4/9*V-V2/9+2/9
aux(41) =< V-V2
aux(42) =< V/2
aux(43) =< V/2-V2/2
aux(44) =< V/3
aux(45) =< V/3-V2/3
aux(46) =< 2/3*V-V2/6+1/3
aux(47) =< V2/3-V11/3
s(167) =< aux(44)
s(165) =< aux(47)
s(126) =< aux(45)
s(127) =< aux(45)
s(128) =< aux(45)
s(129) =< aux(42)
s(127) =< aux(42)
s(129) =< aux(43)
s(127) =< aux(43)
s(129) =< aux(41)
s(127) =< aux(41)
s(130) =< s(119)+1/3
s(131) =< s(129)*s(119)
s(132) =< s(127)*s(130)
s(133) =< aux(44)+1/3
s(134) =< s(129)*aux(44)
s(135) =< s(127)*s(133)
s(136) =< s(118)
s(137) =< aux(42)
s(138) =< aux(42)
s(137) =< aux(41)
s(138) =< aux(41)
s(137) =< s(118)
s(138) =< s(118)
s(138) =< s(116)
s(139) =< s(137)*s(119)
s(140) =< s(138)*s(130)
s(136) =< aux(42)
s(136) =< aux(43)
s(136) =< s(115)
s(141) =< s(136)*aux(44)
s(142) =< s(136)*s(133)
s(143) =< aux(41)
s(144) =< s(129)*s(133)
s(145) =< aux(42)
s(128) =< aux(42)
s(145) =< aux(43)
s(128) =< aux(43)
s(145) =< aux(46)
s(128) =< aux(46)
s(146) =< s(145)*aux(44)
s(147) =< s(128)*s(133)
s(162) =< aux(42)
s(162) =< aux(43)
s(162) =< aux(46)
s(162) =< aux(45)
s(162) =< s(150)
s(164) =< s(162)*s(133)

  with precondition: [V>=0] 


Closed-form bounds of start(V,V2,V11): 
-------------------------------------
* Chain [34] with precondition: [V>=0] 
    - Upper bound: nat(V/3-V2/3)*V+1+V/2*(3*V)+19/3*nat(4/3*V-V2/3+2/3)+V/3*(nat(4/3*V-V2/3+2/3)*2)+nat(V-V2)*7+nat(V/3-2/3*V2)+nat(V/3-V2/3)*30+V/3*(nat(V/3-V2/3)*5)+nat(V2/3-V11/3)*2+55/2*V+V/3*(9/2*V)+2/3*V 
    - Complexity: n^2 

### Maximum cost of start(V,V2,V11): nat(V/3-V2/3)*V+1+V/2*(3*V)+19/3*nat(4/3*V-V2/3+2/3)+V/3*(nat(4/3*V-V2/3+2/3)*2)+nat(V-V2)*7+nat(V/3-2/3*V2)+nat(V/3-V2/3)*30+V/3*(nat(V/3-V2/3)*5)+nat(V2/3-V11/3)*2+55/2*V+V/3*(9/2*V)+2/3*V 
Asymptotic class: n^2 
* Total analysis performed in 624 ms.


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

(16)
BOUNDS(1, n^2)