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


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


WORST_CASE(?, O(n^1))
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(1, max(5 + 8 * Arg_1 + 8 * Arg_3, 21, 13 + 8 * Arg_1)).

(0) CpxIntTrs
(1) Koat2 Proof [FINISHED, 3352 ms]
(2) BOUNDS(1, max(5 + 8 * Arg_1 + 8 * Arg_3, 21, 13 + 8 * Arg_1))


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

(0)
Obligation:
Complexity Int TRS consisting of the following rules:
eval_start_start(v__0, v__01, v_x, v_y) -> Com_1(eval_start_bb0_in(v__0, v__01, v_x, v_y)) :|: TRUE
eval_start_bb0_in(v__0, v__01, v_x, v_y) -> Com_1(eval_start_0(v__0, v__01, v_x, v_y)) :|: TRUE
eval_start_0(v__0, v__01, v_x, v_y) -> Com_1(eval_start_1(v__0, v__01, v_x, v_y)) :|: TRUE
eval_start_1(v__0, v__01, v_x, v_y) -> Com_1(eval_start_2(v__0, v__01, v_x, v_y)) :|: TRUE
eval_start_2(v__0, v__01, v_x, v_y) -> Com_1(eval_start_3(v__0, v__01, v_x, v_y)) :|: TRUE
eval_start_3(v__0, v__01, v_x, v_y) -> Com_1(eval_start_4(v__0, v__01, v_x, v_y)) :|: TRUE
eval_start_4(v__0, v__01, v_x, v_y) -> Com_1(eval_start_5(v__0, v__01, v_x, v_y)) :|: TRUE
eval_start_5(v__0, v__01, v_x, v_y) -> Com_1(eval_start_6(v__0, v__01, v_x, v_y)) :|: TRUE
eval_start_6(v__0, v__01, v_x, v_y) -> Com_1(eval_start_7(v__0, v__01, v_x, v_y)) :|: TRUE
eval_start_7(v__0, v__01, v_x, v_y) -> Com_1(eval_start_bb1_in(v_x, v_y, v_x, v_y)) :|: TRUE
eval_start_bb1_in(v__0, v__01, v_x, v_y) -> Com_1(eval_start_bb2_in(v__0, v__01, v_x, v_y)) :|: v__0 > 0
eval_start_bb1_in(v__0, v__01, v_x, v_y) -> Com_1(eval_start_bb3_in(v__0, v__01, v_x, v_y)) :|: v__0 <= 0
eval_start_bb2_in(v__0, v__01, v_x, v_y) -> Com_1(eval_start_bb1_in(v__01, v__0 - 1, v_x, v_y)) :|: TRUE
eval_start_bb3_in(v__0, v__01, v_x, v_y) -> Com_1(eval_start_stop(v__0, v__01, v_x, v_y)) :|: TRUE

The start-symbols are:[eval_start_start_4]


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

(1) Koat2 Proof (FINISHED)
YES( ?, 13+8*max([1, max([Arg_1, -1+Arg_3+Arg_1])]) {O(n)})



Initial Complexity Problem:

  Start:  evalstartstart  

  Program_Vars:  Arg_0, Arg_1, Arg_2, Arg_3  

  Temp_Vars:    

  Locations:  evalstart0, evalstart1, evalstart2, evalstart3, evalstart4, evalstart5, evalstart6, evalstart7, evalstartbb0in, evalstartbb1in, evalstartbb3in, evalstartstart, evalstartstop  

  Transitions:

  2: evalstart0->evalstart1

  3: evalstart1->evalstart2

  4: evalstart2->evalstart3

  5: evalstart3->evalstart4

  6: evalstart4->evalstart5

  7: evalstart5->evalstart6

  8: evalstart6->evalstart7

  9: evalstart7->evalstartbb1in

  1: evalstartbb0in->evalstart0

  468: evalstartbb1in->evalstartbb1in

  11: evalstartbb1in->evalstartbb3in

  13: evalstartbb3in->evalstartstop

  0: evalstartstart->evalstartbb0in  



Timebounds: 

  Overall timebound: 13+8*max([1, max([Arg_1, -1+Arg_3+Arg_1])]) {O(n)}

  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->evalstart7: 1 {O(1)}

  9: evalstart7->evalstartbb1in: 1 {O(1)}

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

  11: evalstartbb1in->evalstartbb3in: 1 {O(1)}

  468: evalstartbb1in->evalstartbb1in: 1+8*max([1, max([Arg_1, -1+Arg_3+Arg_1])]) {O(n)}

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

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



Costbounds:

  Overall costbound: 12+2*(1+8*max([1, max([Arg_1, -1+Arg_3+Arg_1])])) {O(n)}

  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->evalstart7: 1 {O(1)}

  9: evalstart7->evalstartbb1in: 1 {O(1)}

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

  11: evalstartbb1in->evalstartbb3in: 1 {O(1)}

  468: evalstartbb1in->evalstartbb1in: 2*(1+8*max([1, max([Arg_1, -1+Arg_3+Arg_1])])) {O(n)}

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

  0: evalstartstart->evalstartbb0in: 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)}

  2: evalstart0->evalstart1, Arg_3: Arg_3 {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)}

  3: evalstart1->evalstart2, Arg_3: Arg_3 {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)}

  4: evalstart2->evalstart3, Arg_3: Arg_3 {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)}

  5: evalstart3->evalstart4, Arg_3: Arg_3 {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)}

  6: evalstart4->evalstart5, Arg_3: Arg_3 {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)}

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

  8: evalstart6->evalstart7, Arg_0: Arg_0 {O(n)}

  8: evalstart6->evalstart7, Arg_1: Arg_1 {O(n)}

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

  8: evalstart6->evalstart7, Arg_3: Arg_3 {O(n)}

  9: evalstart7->evalstartbb1in, Arg_0: Arg_1 {O(n)}

  9: evalstart7->evalstartbb1in, Arg_1: Arg_1 {O(n)}

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

  9: evalstart7->evalstartbb1in, Arg_3: Arg_3 {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)}

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

  11: evalstartbb1in->evalstartbb3in, Arg_0: min([0, min([Arg_1, Arg_3])]) {O(n)}

  11: evalstartbb1in->evalstartbb3in, Arg_1: Arg_1 {O(n)}

  11: evalstartbb1in->evalstartbb3in, Arg_2: min([0, Arg_3]) {O(n)}

  11: evalstartbb1in->evalstartbb3in, Arg_3: Arg_3 {O(n)}

  468: evalstartbb1in->evalstartbb1in, Arg_0: min([0, Arg_3]) {O(n)}

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

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

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

  13: evalstartbb3in->evalstartstop, Arg_0: min([0, min([Arg_1, Arg_3])]) {O(n)}

  13: evalstartbb3in->evalstartstop, Arg_1: Arg_1 {O(n)}

  13: evalstartbb3in->evalstartstop, Arg_2: min([0, Arg_3]) {O(n)}

  13: evalstartbb3in->evalstartstop, Arg_3: Arg_3 {O(n)}

  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)}

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

`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)}

  2: evalstart0->evalstart1, Arg_3: Arg_3 {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)}

  3: evalstart1->evalstart2, Arg_3: Arg_3 {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)}

  4: evalstart2->evalstart3, Arg_3: Arg_3 {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)}

  5: evalstart3->evalstart4, Arg_3: Arg_3 {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)}

  6: evalstart4->evalstart5, Arg_3: Arg_3 {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)}

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

  8: evalstart6->evalstart7, Arg_0: Arg_0 {O(n)}

  8: evalstart6->evalstart7, Arg_1: Arg_1 {O(n)}

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

  8: evalstart6->evalstart7, Arg_3: Arg_3 {O(n)}

  9: evalstart7->evalstartbb1in, Arg_0: Arg_1 {O(n)}

  9: evalstart7->evalstartbb1in, Arg_1: Arg_1 {O(n)}

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

  9: evalstart7->evalstartbb1in, Arg_3: Arg_3 {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)}

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

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

  11: evalstartbb1in->evalstartbb3in, Arg_1: Arg_1 {O(n)}

  11: evalstartbb1in->evalstartbb3in, Arg_2: min([max([Arg_3, max([Arg_1, Arg_3])]), min([max([Arg_3, max([Arg_1, Arg_3])]), max([Arg_3, max([Arg_3, Arg_1])])])]) {O(n)}

  11: evalstartbb1in->evalstartbb3in, Arg_3: Arg_3 {O(n)}

  468: evalstartbb1in->evalstartbb1in, Arg_0: max([Arg_1, Arg_3]) {O(n)}

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

  468: evalstartbb1in->evalstartbb1in, Arg_2: max([Arg_1, Arg_3]) {O(n)}

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

  13: evalstartbb3in->evalstartstop, Arg_0: 0 {O(1)}

  13: evalstartbb3in->evalstartstop, Arg_1: Arg_1 {O(n)}

  13: evalstartbb3in->evalstartstop, Arg_2: min([max([Arg_3, max([Arg_3, Arg_1])]), min([max([Arg_3, max([Arg_1, Arg_3])]), min([max([Arg_3, max([Arg_1, Arg_3])]), max([Arg_3, max([Arg_3, Arg_1])])])])]) {O(n)}

  13: evalstartbb3in->evalstartstop, Arg_3: Arg_3 {O(n)}

  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)}

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


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

(2)
BOUNDS(1, max(5 + 8 * Arg_1 + 8 * Arg_3, 21, 13 + 8 * Arg_1))