/export/starexec/sandbox/solver/bin/starexec_run_complexity /export/starexec/sandbox/benchmark/theBenchmark.koat /export/starexec/sandbox/output/output_files


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


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


The runtime complexity of the given CpxIntTrs could be proven to be BOUNDS(n^1, 2 * max(1, 3 + 2 * Arg_2) * max(2, 4 + 2 * Arg_2) + max(9, 10 + Arg_2) + max(6, 8 + 2 * Arg_2)).

(0) CpxIntTrs
(1) Koat2 Proof [FINISHED, 3741 ms]
(2) BOUNDS(1, 2 * max(1, 3 + 2 * Arg_2) * max(2, 4 + 2 * Arg_2) + max(9, 10 + Arg_2) + max(6, 8 + 2 * Arg_2))
(3) Loat Proof [FINISHED, 624 ms]
(4) BOUNDS(n^1, INF)


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

(0)
Obligation:
Complexity Int TRS consisting of the following rules:
eval_start_start(v_n, v_x_0, v_y_0) -> Com_1(eval_start_bb0_in(v_n, v_x_0, v_y_0)) :|: TRUE
eval_start_bb0_in(v_n, v_x_0, v_y_0) -> Com_1(eval_start_0(v_n, v_x_0, v_y_0)) :|: TRUE
eval_start_0(v_n, v_x_0, v_y_0) -> Com_1(eval_start_1(v_n, v_x_0, v_y_0)) :|: TRUE
eval_start_1(v_n, v_x_0, v_y_0) -> Com_1(eval_start_2(v_n, v_x_0, v_y_0)) :|: TRUE
eval_start_2(v_n, v_x_0, v_y_0) -> Com_1(eval_start_3(v_n, v_x_0, v_y_0)) :|: TRUE
eval_start_3(v_n, v_x_0, v_y_0) -> Com_1(eval_start_4(v_n, v_x_0, v_y_0)) :|: TRUE
eval_start_4(v_n, v_x_0, v_y_0) -> Com_1(eval_start_5(v_n, v_x_0, v_y_0)) :|: TRUE
eval_start_5(v_n, v_x_0, v_y_0) -> Com_1(eval_start_6(v_n, v_x_0, v_y_0)) :|: TRUE
eval_start_6(v_n, v_x_0, v_y_0) -> Com_1(eval_start_bb1_in(v_n, 0, 0)) :|: TRUE
eval_start_bb1_in(v_n, v_x_0, v_y_0) -> Com_1(eval_start_bb2_in(v_n, v_x_0, v_y_0)) :|: v_x_0 < v_n
eval_start_bb1_in(v_n, v_x_0, v_y_0) -> Com_1(eval_start_bb3_in(v_n, v_x_0, v_y_0)) :|: v_x_0 >= v_n
eval_start_bb2_in(v_n, v_x_0, v_y_0) -> Com_1(eval_start_bb1_in(v_n, v_x_0 + 1, v_y_0 + 1)) :|: TRUE
eval_start_bb3_in(v_n, v_x_0, v_y_0) -> Com_1(eval_start_bb4_in(v_n, v_x_0, v_y_0)) :|: v_y_0 > 0
eval_start_bb3_in(v_n, v_x_0, v_y_0) -> Com_1(eval_start_bb5_in(v_n, v_x_0, v_y_0)) :|: v_y_0 <= 0
eval_start_bb4_in(v_n, v_x_0, v_y_0) -> Com_1(eval_start_bb1_in(v_n, v_x_0, v_y_0 - 1)) :|: TRUE
eval_start_bb5_in(v_n, v_x_0, v_y_0) -> Com_1(eval_start_stop(v_n, v_x_0, v_y_0)) :|: TRUE

The start-symbols are:[eval_start_start_3]


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

(1) Koat2 Proof (FINISHED)
YES( ?, 4+1+max([1, 1+2*(1+Arg_2)])+max([9, 10+Arg_2])+max([1, 1+2*(1+Arg_2)])*max([2, 2+2*(1+Arg_2)])+max([1, 1+2*(1+Arg_2)])*max([2, 2+2*(1+Arg_2)]) {O(n^2)})



Initial Complexity Problem:

  Start:  evalstartstart  

  Program_Vars:  Arg_0, Arg_1, Arg_2  

  Temp_Vars:  Arg1_P  

  Locations:  evalstart0, evalstart1, evalstart2, evalstart3, evalstart4, evalstart5, evalstart6, evalstartbb0in, evalstartbb1in, evalstartbb2in, evalstartbb3in, evalstartbb5in, evalstartstart, evalstartstop, n_evalstartbb1in___1  

  Transitions:

  2: evalstart0->evalstart1

  3: evalstart1->evalstart2

  4: evalstart2->evalstart3

  5: evalstart3->evalstart4

  6: evalstart4->evalstart5

  7: evalstart5->evalstart6

  8: evalstart6->evalstartbb1in

  1: evalstartbb0in->evalstart0

  9: evalstartbb1in->evalstartbb2in

  468: evalstartbb1in->n_evalstartbb1in___1

  11: evalstartbb2in->evalstartbb1in

  13: evalstartbb3in->evalstartbb5in

  15: evalstartbb5in->evalstartstop

  0: evalstartstart->evalstartbb0in

  475: n_evalstartbb1in___1->evalstartbb2in

  467: n_evalstartbb1in___1->n_evalstartbb1in___1  



Timebounds: 

  Overall timebound: 4+1+max([1, 1+2*(1+Arg_2)])+max([9, 10+Arg_2])+max([1, 1+2*(1+Arg_2)])*max([2, 2+2*(1+Arg_2)])+max([1, 1+2*(1+Arg_2)])*max([2, 2+2*(1+Arg_2)]) {O(n^2)}

  2: evalstart0->evalstart1: 1 {O(1)}

  3: evalstart1->evalstart2: 1 {O(1)}

  4: evalstart2->evalstart3: 1 {O(1)}

  5: evalstart3->evalstart4: 1 {O(1)}

  6: evalstart4->evalstart5: 1 {O(1)}

  7: evalstart5->evalstart6: 1 {O(1)}

  8: evalstart6->evalstartbb1in: 1 {O(1)}

  1: evalstartbb0in->evalstart0: 1 {O(1)}

  9: evalstartbb1in->evalstartbb2in: max([0, 1+Arg_2]) {O(n)}

  468: evalstartbb1in->n_evalstartbb1in___1: 1 {O(1)}

  11: evalstartbb2in->evalstartbb1in: max([1, 1+2*(1+Arg_2)]) {O(n)}

  13: evalstartbb3in->evalstartbb5in: 1 {O(1)}

  15: evalstartbb5in->evalstartstop: 1 {O(1)}

  0: evalstartstart->evalstartbb0in: 1 {O(1)}

  467: n_evalstartbb1in___1->n_evalstartbb1in___1: 1+max([1, 1+2*(1+Arg_2)])*max([2, 2+2*(1+Arg_2)])+max([1, 1+2*(1+Arg_2)])*max([2, 2+2*(1+Arg_2)]) {O(n^2)}

  475: n_evalstartbb1in___1->evalstartbb2in: 1 {O(1)}



Costbounds:

  Overall costbound: 4+3*(1+max([1, 1+2*(1+Arg_2)])*max([2, 2+2*(1+Arg_2)])+max([1, 1+2*(1+Arg_2)])*max([2, 2+2*(1+Arg_2)]))+max([1, 1+2*(1+Arg_2)])+max([11, 12+Arg_2]) {O(n^2)}

  2: evalstart0->evalstart1: 1 {O(1)}

  3: evalstart1->evalstart2: 1 {O(1)}

  4: evalstart2->evalstart3: 1 {O(1)}

  5: evalstart3->evalstart4: 1 {O(1)}

  6: evalstart4->evalstart5: 1 {O(1)}

  7: evalstart5->evalstart6: 1 {O(1)}

  8: evalstart6->evalstartbb1in: 1 {O(1)}

  1: evalstartbb0in->evalstart0: 1 {O(1)}

  9: evalstartbb1in->evalstartbb2in: max([0, 1+Arg_2]) {O(n)}

  468: evalstartbb1in->n_evalstartbb1in___1: 3 {O(1)}

  11: evalstartbb2in->evalstartbb1in: max([1, 1+2*(1+Arg_2)]) {O(n)}

  13: evalstartbb3in->evalstartbb5in: 1 {O(1)}

  15: evalstartbb5in->evalstartstop: 1 {O(1)}

  0: evalstartstart->evalstartbb0in: 1 {O(1)}

  467: n_evalstartbb1in___1->n_evalstartbb1in___1: 3*(1+max([1, 1+2*(1+Arg_2)])*max([2, 2+2*(1+Arg_2)])+max([1, 1+2*(1+Arg_2)])*max([2, 2+2*(1+Arg_2)])) {O(n^2)}

  475: n_evalstartbb1in___1->evalstartbb2in: 1 {O(1)}



Sizebounds:

`Lower:

  2: evalstart0->evalstart1, Arg_0: Arg_0 {O(n)}

  2: evalstart0->evalstart1, Arg_1: Arg_1 {O(n)}

  2: evalstart0->evalstart1, Arg_2: Arg_2 {O(n)}

  3: evalstart1->evalstart2, Arg_0: Arg_0 {O(n)}

  3: evalstart1->evalstart2, Arg_1: Arg_1 {O(n)}

  3: evalstart1->evalstart2, Arg_2: Arg_2 {O(n)}

  4: evalstart2->evalstart3, Arg_0: Arg_0 {O(n)}

  4: evalstart2->evalstart3, Arg_1: Arg_1 {O(n)}

  4: evalstart2->evalstart3, Arg_2: Arg_2 {O(n)}

  5: evalstart3->evalstart4, Arg_0: Arg_0 {O(n)}

  5: evalstart3->evalstart4, Arg_1: Arg_1 {O(n)}

  5: evalstart3->evalstart4, Arg_2: Arg_2 {O(n)}

  6: evalstart4->evalstart5, Arg_0: Arg_0 {O(n)}

  6: evalstart4->evalstart5, Arg_1: Arg_1 {O(n)}

  6: evalstart4->evalstart5, Arg_2: Arg_2 {O(n)}

  7: evalstart5->evalstart6, Arg_0: Arg_0 {O(n)}

  7: evalstart5->evalstart6, Arg_1: Arg_1 {O(n)}

  7: evalstart5->evalstart6, Arg_2: Arg_2 {O(n)}

  8: evalstart6->evalstartbb1in, Arg_0: 0 {O(1)}

  8: evalstart6->evalstartbb1in, Arg_1: 0 {O(1)}

  8: evalstart6->evalstartbb1in, Arg_2: Arg_2 {O(n)}

  1: evalstartbb0in->evalstart0, Arg_0: Arg_0 {O(n)}

  1: evalstartbb0in->evalstart0, Arg_1: Arg_1 {O(n)}

  1: evalstartbb0in->evalstart0, Arg_2: Arg_2 {O(n)}

  9: evalstartbb1in->evalstartbb2in, Arg_0: 0 {O(1)}

  9: evalstartbb1in->evalstartbb2in, Arg_1: 0 {O(1)}

  9: evalstartbb1in->evalstartbb2in, Arg_2: Arg_2 {O(n)}

  468: evalstartbb1in->n_evalstartbb1in___1, Arg_0: 0 {O(1)}

  468: evalstartbb1in->n_evalstartbb1in___1, Arg_1: 0 {O(1)}

  468: evalstartbb1in->n_evalstartbb1in___1, Arg_2: Arg_2 {O(n)}

  11: evalstartbb2in->evalstartbb1in, Arg_0: 0 {O(1)}

  11: evalstartbb2in->evalstartbb1in, Arg_1: 0 {O(1)}

  11: evalstartbb2in->evalstartbb1in, Arg_2: Arg_2 {O(n)}

  13: evalstartbb3in->evalstartbb5in, Arg_0: inf {Infinity}

  13: evalstartbb3in->evalstartbb5in, Arg_1: inf {Infinity}

  13: evalstartbb3in->evalstartbb5in, Arg_2: inf {Infinity}

  15: evalstartbb5in->evalstartstop, Arg_0: inf {Infinity}

  15: evalstartbb5in->evalstartstop, Arg_1: inf {Infinity}

  15: evalstartbb5in->evalstartstop, Arg_2: inf {Infinity}

  0: evalstartstart->evalstartbb0in, Arg_0: Arg_0 {O(n)}

  0: evalstartstart->evalstartbb0in, Arg_1: Arg_1 {O(n)}

  0: evalstartstart->evalstartbb0in, Arg_2: Arg_2 {O(n)}

  467: n_evalstartbb1in___1->n_evalstartbb1in___1, Arg_0: 0 {O(1)}

  467: n_evalstartbb1in___1->n_evalstartbb1in___1, Arg_1: 0 {O(1)}

  467: n_evalstartbb1in___1->n_evalstartbb1in___1, Arg_2: Arg_2 {O(n)}

  475: n_evalstartbb1in___1->evalstartbb2in, Arg_0: inf {Infinity}

  475: n_evalstartbb1in___1->evalstartbb2in, Arg_1: inf {Infinity}

  475: n_evalstartbb1in___1->evalstartbb2in, Arg_2: inf {Infinity}

`Upper:

  2: evalstart0->evalstart1, Arg_0: Arg_0 {O(n)}

  2: evalstart0->evalstart1, Arg_1: Arg_1 {O(n)}

  2: evalstart0->evalstart1, Arg_2: Arg_2 {O(n)}

  3: evalstart1->evalstart2, Arg_0: Arg_0 {O(n)}

  3: evalstart1->evalstart2, Arg_1: Arg_1 {O(n)}

  3: evalstart1->evalstart2, Arg_2: Arg_2 {O(n)}

  4: evalstart2->evalstart3, Arg_0: Arg_0 {O(n)}

  4: evalstart2->evalstart3, Arg_1: Arg_1 {O(n)}

  4: evalstart2->evalstart3, Arg_2: Arg_2 {O(n)}

  5: evalstart3->evalstart4, Arg_0: Arg_0 {O(n)}

  5: evalstart3->evalstart4, Arg_1: Arg_1 {O(n)}

  5: evalstart3->evalstart4, Arg_2: Arg_2 {O(n)}

  6: evalstart4->evalstart5, Arg_0: Arg_0 {O(n)}

  6: evalstart4->evalstart5, Arg_1: Arg_1 {O(n)}

  6: evalstart4->evalstart5, Arg_2: Arg_2 {O(n)}

  7: evalstart5->evalstart6, Arg_0: Arg_0 {O(n)}

  7: evalstart5->evalstart6, Arg_1: Arg_1 {O(n)}

  7: evalstart5->evalstart6, Arg_2: Arg_2 {O(n)}

  8: evalstart6->evalstartbb1in, Arg_0: 0 {O(1)}

  8: evalstart6->evalstartbb1in, Arg_1: 0 {O(1)}

  8: evalstart6->evalstartbb1in, Arg_2: Arg_2 {O(n)}

  1: evalstartbb0in->evalstart0, Arg_0: Arg_0 {O(n)}

  1: evalstartbb0in->evalstart0, Arg_1: Arg_1 {O(n)}

  1: evalstartbb0in->evalstart0, Arg_2: Arg_2 {O(n)}

  9: evalstartbb1in->evalstartbb2in, Arg_0: max([1, 1+2*(1+Arg_2)]) {O(n)}

  9: evalstartbb1in->evalstartbb2in, Arg_1: max([1, 1+2*(1+Arg_2)]) {O(n)}

  9: evalstartbb1in->evalstartbb2in, Arg_2: Arg_2 {O(n)}

  468: evalstartbb1in->n_evalstartbb1in___1, Arg_0: max([1, 1+2*(1+Arg_2)]) {O(n)}

  468: evalstartbb1in->n_evalstartbb1in___1, Arg_2: Arg_2 {O(n)}

  11: evalstartbb2in->evalstartbb1in, Arg_0: max([1, 1+2*(1+Arg_2)]) {O(n)}

  11: evalstartbb2in->evalstartbb1in, Arg_1: max([1, 1+2*(1+Arg_2)]) {O(n)}

  11: evalstartbb2in->evalstartbb1in, Arg_2: Arg_2 {O(n)}

  13: evalstartbb3in->evalstartbb5in, Arg_0: -(inf) {Infinity}

  13: evalstartbb3in->evalstartbb5in, Arg_1: -(inf) {Infinity}

  13: evalstartbb3in->evalstartbb5in, Arg_2: -(inf) {Infinity}

  15: evalstartbb5in->evalstartstop, Arg_0: -(inf) {Infinity}

  15: evalstartbb5in->evalstartstop, Arg_1: -(inf) {Infinity}

  15: evalstartbb5in->evalstartstop, Arg_2: -(inf) {Infinity}

  0: evalstartstart->evalstartbb0in, Arg_0: Arg_0 {O(n)}

  0: evalstartstart->evalstartbb0in, Arg_1: Arg_1 {O(n)}

  0: evalstartstart->evalstartbb0in, Arg_2: Arg_2 {O(n)}

  467: n_evalstartbb1in___1->n_evalstartbb1in___1, Arg_0: max([1, 1+2*(1+Arg_2)]) {O(n)}

  467: n_evalstartbb1in___1->n_evalstartbb1in___1, Arg_2: Arg_2 {O(n)}

  475: n_evalstartbb1in___1->evalstartbb2in, Arg_0: -(inf) {Infinity}

  475: n_evalstartbb1in___1->evalstartbb2in, Arg_1: -(inf) {Infinity}

  475: n_evalstartbb1in___1->evalstartbb2in, Arg_2: -(inf) {Infinity}


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

(2)
BOUNDS(1, 2 * max(1, 3 + 2 * Arg_2) * max(2, 4 + 2 * Arg_2) + max(9, 10 + Arg_2) + max(6, 8 + 2 * Arg_2))

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

(3) Loat Proof (FINISHED)


### Pre-processing the ITS problem ###



Initial linear ITS problem

   Start location: evalstartstart

      0: evalstartstart -> evalstartbb0in : [], cost: 1

      1: evalstartbb0in -> evalstart0 : [], cost: 1

      2: evalstart0 -> evalstart1 : [], cost: 1

      3: evalstart1 -> evalstart2 : [], cost: 1

      4: evalstart2 -> evalstart3 : [], cost: 1

      5: evalstart3 -> evalstart4 : [], cost: 1

      6: evalstart4 -> evalstart5 : [], cost: 1

      7: evalstart5 -> evalstart6 : [], cost: 1

      8: evalstart6 -> evalstartbb1in : A'=0, B'=0, [], cost: 1

      9: evalstartbb1in -> evalstartbb2in : [ C>=1+A ], cost: 1

     10: evalstartbb1in -> evalstartbb3in : [ A>=C ], cost: 1

     11: evalstartbb2in -> evalstartbb1in : A'=1+A, B'=1+B, [], cost: 1

     12: evalstartbb3in -> evalstartbb4in : [ B>=1 ], cost: 1

     13: evalstartbb3in -> evalstartbb5in : [ 0>=B ], cost: 1

     14: evalstartbb4in -> evalstartbb1in : B'=-1+B, [], cost: 1

     15: evalstartbb5in -> evalstartstop : [], cost: 1



Checking for constant complexity:

   The following rule is satisfiable with cost >= 1, yielding constant complexity:

      0: evalstartstart -> evalstartbb0in : [], cost: 1



Removed unreachable and leaf rules:

   Start location: evalstartstart

      0: evalstartstart -> evalstartbb0in : [], cost: 1

      1: evalstartbb0in -> evalstart0 : [], cost: 1

      2: evalstart0 -> evalstart1 : [], cost: 1

      3: evalstart1 -> evalstart2 : [], cost: 1

      4: evalstart2 -> evalstart3 : [], cost: 1

      5: evalstart3 -> evalstart4 : [], cost: 1

      6: evalstart4 -> evalstart5 : [], cost: 1

      7: evalstart5 -> evalstart6 : [], cost: 1

      8: evalstart6 -> evalstartbb1in : A'=0, B'=0, [], cost: 1

      9: evalstartbb1in -> evalstartbb2in : [ C>=1+A ], cost: 1

     10: evalstartbb1in -> evalstartbb3in : [ A>=C ], cost: 1

     11: evalstartbb2in -> evalstartbb1in : A'=1+A, B'=1+B, [], cost: 1

     12: evalstartbb3in -> evalstartbb4in : [ B>=1 ], cost: 1

     14: evalstartbb4in -> evalstartbb1in : B'=-1+B, [], cost: 1



### Simplification by acceleration and chaining ###



Eliminated locations (on linear paths):

   Start location: evalstartstart

     23: evalstartstart -> evalstartbb1in : A'=0, B'=0, [], cost: 9

     24: evalstartbb1in -> evalstartbb1in : A'=1+A, B'=1+B, [ C>=1+A ], cost: 2

     26: evalstartbb1in -> evalstartbb1in : B'=-1+B, [ A>=C && B>=1 ], cost: 3



Accelerating simple loops of location 9.

   Accelerating the following rules:

     24: evalstartbb1in -> evalstartbb1in : A'=1+A, B'=1+B, [ C>=1+A ], cost: 2

     26: evalstartbb1in -> evalstartbb1in : B'=-1+B, [ A>=C && B>=1 ], cost: 3



   Accelerated rule 24 with metering function C-A, yielding the new rule 27.

   Accelerated rule 26 with metering function B, yielding the new rule 28.

   Removing the simple loops: 24 26.



Accelerated all simple loops using metering functions (where possible):

   Start location: evalstartstart

     23: evalstartstart -> evalstartbb1in : A'=0, B'=0, [], cost: 9

     27: evalstartbb1in -> evalstartbb1in : A'=C, B'=C-A+B, [ C>=1+A ], cost: 2*C-2*A

     28: evalstartbb1in -> evalstartbb1in : B'=0, [ A>=C && B>=1 ], cost: 3*B



Chained accelerated rules (with incoming rules):

   Start location: evalstartstart

     23: evalstartstart -> evalstartbb1in : A'=0, B'=0, [], cost: 9

     29: evalstartstart -> evalstartbb1in : A'=C, B'=C, [ C>=1 ], cost: 9+2*C



Removed unreachable locations (and leaf rules with constant cost):

   Start location: evalstartstart

     29: evalstartstart -> evalstartbb1in : A'=C, B'=C, [ C>=1 ], cost: 9+2*C



### Computing asymptotic complexity ###



Fully simplified ITS problem

   Start location: evalstartstart

     29: evalstartstart -> evalstartbb1in : A'=C, B'=C, [ C>=1 ], cost: 9+2*C



Computing asymptotic complexity for rule 29

   Solved the limit problem by the following transformations:

      Created initial limit problem:

      C (+/+!), 9+2*C (+) [not solved]



      removing all constraints (solved by SMT)

      resulting limit problem: [solved]



      applying transformation rule (C) using substitution {C==n}

      resulting limit problem:

      [solved]



   Solution:

      C / n

   Resulting cost 9+2*n has complexity: Poly(n^1)



Found new complexity Poly(n^1).



Obtained the following overall complexity (w.r.t. the length of the input n):

   Complexity:  Poly(n^1)

   Cpx degree:  1

   Solved cost: 9+2*n

   Rule cost:   9+2*C

   Rule guard:  [ C>=1 ]



WORST_CASE(Omega(n^1),?)


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

(4)
BOUNDS(n^1, INF)