/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(6, 14 + 4 * Arg_0 + 4 * Arg_1 + -4 * Arg_2) + nat(8 + 4 * Arg_0 + 4 * Arg_1 + -4 * Arg_2) + nat(2 + Arg_0 + Arg_1 + -1 * Arg_2)).

(0) CpxIntTrs
(1) Koat2 Proof [FINISHED, 1008 ms]
(2) BOUNDS(1, max(6, 14 + 4 * Arg_0 + 4 * Arg_1 + -4 * Arg_2) + nat(8 + 4 * Arg_0 + 4 * Arg_1 + -4 * Arg_2) + nat(2 + Arg_0 + Arg_1 + -1 * Arg_2))


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

(0)
Obligation:
Complexity Int TRS consisting of the following rules:
evalaaron2start(A, B, C) -> Com_1(evalaaron2entryin(A, B, C)) :|: TRUE
evalaaron2entryin(A, B, C) -> Com_1(evalaaron2bb6in(A, C, B)) :|: A >= 0
evalaaron2entryin(A, B, C) -> Com_1(evalaaron2returnin(A, B, C)) :|: 0 >= A + 1
evalaaron2bb6in(A, B, C) -> Com_1(evalaaron2returnin(A, B, C)) :|: B >= C + 1
evalaaron2bb6in(A, B, C) -> Com_1(evalaaron2returnin(A, B, C)) :|: 0 >= A + 1
evalaaron2bb6in(A, B, C) -> Com_1(evalaaron2bb3in(A, B, C)) :|: C >= B && A >= 0
evalaaron2bb3in(A, B, C) -> Com_1(evalaaron2bb4in(A, B, C)) :|: 0 >= D + 1
evalaaron2bb3in(A, B, C) -> Com_1(evalaaron2bb4in(A, B, C)) :|: D >= 1
evalaaron2bb3in(A, B, C) -> Com_1(evalaaron2bb5in(A, B, C)) :|: TRUE
evalaaron2bb4in(A, B, C) -> Com_1(evalaaron2bb6in(A, B, C - A - 1)) :|: TRUE
evalaaron2bb5in(A, B, C) -> Com_1(evalaaron2bb6in(A, B + A + 1, C)) :|: TRUE
evalaaron2returnin(A, B, C) -> Com_1(evalaaron2stop(A, B, C)) :|: TRUE

The start-symbols are:[evalaaron2start_3]


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

(1) Koat2 Proof (FINISHED)
YES( ?, 6+2*max([0, 2*(2+Arg_1+Arg_0-Arg_2)])+2*max([0, 2+Arg_1+Arg_0-Arg_2])+max([0, 2+Arg_1+Arg_0-Arg_2])+max([0, 2*(2+Arg_1+Arg_0-Arg_2)]) {O(n)})



Initial Complexity Problem:

  Start:  evalaaron2start  

  Program_Vars:  Arg_0, Arg_1, Arg_2  

  Temp_Vars:  D  

  Locations:  evalaaron2bb3in, evalaaron2bb4in, evalaaron2bb5in, evalaaron2bb6in, evalaaron2entryin, evalaaron2returnin, evalaaron2start, evalaaron2stop  

  Transitions:

  6: evalaaron2bb3in->evalaaron2bb4in

  7: evalaaron2bb3in->evalaaron2bb4in

  8: evalaaron2bb3in->evalaaron2bb5in

  9: evalaaron2bb4in->evalaaron2bb6in

  10: evalaaron2bb5in->evalaaron2bb6in

  5: evalaaron2bb6in->evalaaron2bb3in

  3: evalaaron2bb6in->evalaaron2returnin

  4: evalaaron2bb6in->evalaaron2returnin

  1: evalaaron2entryin->evalaaron2bb6in

  2: evalaaron2entryin->evalaaron2returnin

  11: evalaaron2returnin->evalaaron2stop

  0: evalaaron2start->evalaaron2entryin  



Timebounds: 

  Overall timebound: 6+2*max([0, 2*(2+Arg_1+Arg_0-Arg_2)])+2*max([0, 2+Arg_1+Arg_0-Arg_2])+max([0, 2+Arg_1+Arg_0-Arg_2])+max([0, 2*(2+Arg_1+Arg_0-Arg_2)]) {O(n)}

  6: evalaaron2bb3in->evalaaron2bb4in: max([0, 2*(2+Arg_1+Arg_0-Arg_2)]) {O(n)}

  7: evalaaron2bb3in->evalaaron2bb4in: max([0, 2*(2+Arg_1+Arg_0-Arg_2)]) {O(n)}

  8: evalaaron2bb3in->evalaaron2bb5in: max([0, 2*(2+Arg_1+Arg_0-Arg_2)]) {O(n)}

  9: evalaaron2bb4in->evalaaron2bb6in: max([0, 2+Arg_1+Arg_0-Arg_2]) {O(n)}

  10: evalaaron2bb5in->evalaaron2bb6in: max([0, 2+Arg_1+Arg_0-Arg_2]) {O(n)}

  3: evalaaron2bb6in->evalaaron2returnin: 1 {O(1)}

  4: evalaaron2bb6in->evalaaron2returnin: 1 {O(1)}

  5: evalaaron2bb6in->evalaaron2bb3in: max([0, 2+Arg_1+Arg_0-Arg_2]) {O(n)}

  1: evalaaron2entryin->evalaaron2bb6in: 1 {O(1)}

  2: evalaaron2entryin->evalaaron2returnin: 1 {O(1)}

  11: evalaaron2returnin->evalaaron2stop: 1 {O(1)}

  0: evalaaron2start->evalaaron2entryin: 1 {O(1)}



Costbounds:

  Overall costbound: 6+2*max([0, 2*(2+Arg_1+Arg_0-Arg_2)])+2*max([0, 2+Arg_1+Arg_0-Arg_2])+max([0, 2+Arg_1+Arg_0-Arg_2])+max([0, 2*(2+Arg_1+Arg_0-Arg_2)]) {O(n)}

  6: evalaaron2bb3in->evalaaron2bb4in: max([0, 2*(2+Arg_1+Arg_0-Arg_2)]) {O(n)}

  7: evalaaron2bb3in->evalaaron2bb4in: max([0, 2*(2+Arg_1+Arg_0-Arg_2)]) {O(n)}

  8: evalaaron2bb3in->evalaaron2bb5in: max([0, 2*(2+Arg_1+Arg_0-Arg_2)]) {O(n)}

  9: evalaaron2bb4in->evalaaron2bb6in: max([0, 2+Arg_1+Arg_0-Arg_2]) {O(n)}

  10: evalaaron2bb5in->evalaaron2bb6in: max([0, 2+Arg_1+Arg_0-Arg_2]) {O(n)}

  3: evalaaron2bb6in->evalaaron2returnin: 1 {O(1)}

  4: evalaaron2bb6in->evalaaron2returnin: 1 {O(1)}

  5: evalaaron2bb6in->evalaaron2bb3in: max([0, 2+Arg_1+Arg_0-Arg_2]) {O(n)}

  1: evalaaron2entryin->evalaaron2bb6in: 1 {O(1)}

  2: evalaaron2entryin->evalaaron2returnin: 1 {O(1)}

  11: evalaaron2returnin->evalaaron2stop: 1 {O(1)}

  0: evalaaron2start->evalaaron2entryin: 1 {O(1)}



Sizebounds:

`Lower:

  6: evalaaron2bb3in->evalaaron2bb4in, Arg_0: 0 {O(1)}

  6: evalaaron2bb3in->evalaaron2bb4in, Arg_1: min([0, Arg_2]) {O(n)}

  6: evalaaron2bb3in->evalaaron2bb4in, Arg_2: min([0, Arg_1])-max([0, (2+Arg_1+Arg_0-Arg_2)*max([1, 1+Arg_0])]) {O(n^2)}

  7: evalaaron2bb3in->evalaaron2bb4in, Arg_0: 0 {O(1)}

  7: evalaaron2bb3in->evalaaron2bb4in, Arg_1: min([0, Arg_2]) {O(n)}

  7: evalaaron2bb3in->evalaaron2bb4in, Arg_2: min([0, Arg_1])-max([0, (2+Arg_1+Arg_0-Arg_2)*max([1, 1+Arg_0])]) {O(n^2)}

  8: evalaaron2bb3in->evalaaron2bb5in, Arg_0: 0 {O(1)}

  8: evalaaron2bb3in->evalaaron2bb5in, Arg_1: min([0, Arg_2]) {O(n)}

  8: evalaaron2bb3in->evalaaron2bb5in, Arg_2: min([0, Arg_1])-max([0, (2+Arg_1+Arg_0-Arg_2)*max([1, 1+Arg_0])]) {O(n^2)}

  9: evalaaron2bb4in->evalaaron2bb6in, Arg_0: 0 {O(1)}

  9: evalaaron2bb4in->evalaaron2bb6in, Arg_1: min([0, Arg_2]) {O(n)}

  9: evalaaron2bb4in->evalaaron2bb6in, Arg_2: min([0, Arg_1])-max([0, (2+Arg_1+Arg_0-Arg_2)*max([1, 1+Arg_0])]) {O(n^2)}

  10: evalaaron2bb5in->evalaaron2bb6in, Arg_0: 0 {O(1)}

  10: evalaaron2bb5in->evalaaron2bb6in, Arg_1: min([0, Arg_2]) {O(n)}

  10: evalaaron2bb5in->evalaaron2bb6in, Arg_2: min([0, Arg_1])-max([0, (2+Arg_1+Arg_0-Arg_2)*max([1, 1+Arg_0])]) {O(n^2)}

  3: evalaaron2bb6in->evalaaron2returnin, Arg_0: 0 {O(1)}

  3: evalaaron2bb6in->evalaaron2returnin, Arg_1: min([0, Arg_2]) {O(n)}

  3: evalaaron2bb6in->evalaaron2returnin, Arg_2: min([Arg_1, -(max([0, -(Arg_1)])+max([0, (2+Arg_1+Arg_0-Arg_2)*max([1, 1+Arg_0])]))]) {O(n^2)}

  4: evalaaron2bb6in->evalaaron2returnin, Arg_0: 0 {O(1)}

  4: evalaaron2bb6in->evalaaron2returnin, Arg_1: min([0, Arg_2]) {O(n)}

  4: evalaaron2bb6in->evalaaron2returnin, Arg_2: min([0, Arg_1])-max([0, (2+Arg_1+Arg_0-Arg_2)*max([1, 1+Arg_0])]) {O(n^2)}

  5: evalaaron2bb6in->evalaaron2bb3in, Arg_0: 0 {O(1)}

  5: evalaaron2bb6in->evalaaron2bb3in, Arg_1: min([0, Arg_2]) {O(n)}

  5: evalaaron2bb6in->evalaaron2bb3in, Arg_2: min([0, Arg_1])-max([0, (2+Arg_1+Arg_0-Arg_2)*max([1, 1+Arg_0])]) {O(n^2)}

  1: evalaaron2entryin->evalaaron2bb6in, Arg_0: 0 {O(1)}

  1: evalaaron2entryin->evalaaron2bb6in, Arg_1: Arg_2 {O(n)}

  1: evalaaron2entryin->evalaaron2bb6in, Arg_2: Arg_1 {O(n)}

  2: evalaaron2entryin->evalaaron2returnin, Arg_0: Arg_0 {O(n)}

  2: evalaaron2entryin->evalaaron2returnin, Arg_1: Arg_1 {O(n)}

  2: evalaaron2entryin->evalaaron2returnin, Arg_2: Arg_2 {O(n)}

  11: evalaaron2returnin->evalaaron2stop, Arg_0: min([0, Arg_0]) {O(n)}

  11: evalaaron2returnin->evalaaron2stop, Arg_1: min([0, min([Arg_1, Arg_2])]) {O(n)}

  11: evalaaron2returnin->evalaaron2stop, Arg_2: min([Arg_1, min([Arg_2, -(max([0, -(Arg_1)])+max([0, (2+Arg_1+Arg_0-Arg_2)*max([1, 1+Arg_0])]))])]) {O(n^2)}

  0: evalaaron2start->evalaaron2entryin, Arg_0: Arg_0 {O(n)}

  0: evalaaron2start->evalaaron2entryin, Arg_1: Arg_1 {O(n)}

  0: evalaaron2start->evalaaron2entryin, Arg_2: Arg_2 {O(n)}

`Upper:

  6: evalaaron2bb3in->evalaaron2bb4in, Arg_0: Arg_0 {O(n)}

  6: evalaaron2bb3in->evalaaron2bb4in, Arg_1: max([Arg_2, Arg_0])+max([0, (2+Arg_1+Arg_0-Arg_2)*max([1, 1+Arg_0])]) {O(n^2)}

  6: evalaaron2bb3in->evalaaron2bb4in, Arg_2: max([Arg_0, max([Arg_1, Arg_0])]) {O(n)}

  7: evalaaron2bb3in->evalaaron2bb4in, Arg_0: Arg_0 {O(n)}

  7: evalaaron2bb3in->evalaaron2bb4in, Arg_1: max([Arg_2, Arg_0])+max([0, (2+Arg_1+Arg_0-Arg_2)*max([1, 1+Arg_0])]) {O(n^2)}

  7: evalaaron2bb3in->evalaaron2bb4in, Arg_2: max([Arg_0, max([Arg_1, Arg_0])]) {O(n)}

  8: evalaaron2bb3in->evalaaron2bb5in, Arg_0: Arg_0 {O(n)}

  8: evalaaron2bb3in->evalaaron2bb5in, Arg_1: max([Arg_2, Arg_0])+max([0, (2+Arg_1+Arg_0-Arg_2)*max([1, 1+Arg_0])]) {O(n^2)}

  8: evalaaron2bb3in->evalaaron2bb5in, Arg_2: max([Arg_0, max([Arg_1, Arg_0])]) {O(n)}

  9: evalaaron2bb4in->evalaaron2bb6in, Arg_0: Arg_0 {O(n)}

  9: evalaaron2bb4in->evalaaron2bb6in, Arg_1: max([Arg_2, Arg_0])+max([0, (2+Arg_1+Arg_0-Arg_2)*max([1, 1+Arg_0])]) {O(n^2)}

  9: evalaaron2bb4in->evalaaron2bb6in, Arg_2: max([Arg_0, max([Arg_1, Arg_0])]) {O(n)}

  10: evalaaron2bb5in->evalaaron2bb6in, Arg_0: Arg_0 {O(n)}

  10: evalaaron2bb5in->evalaaron2bb6in, Arg_1: max([Arg_2, Arg_0])+max([0, (2+Arg_1+Arg_0-Arg_2)*max([1, 1+Arg_0])]) {O(n^2)}

  10: evalaaron2bb5in->evalaaron2bb6in, Arg_2: max([Arg_0, max([Arg_1, Arg_0])]) {O(n)}

  3: evalaaron2bb6in->evalaaron2returnin, Arg_0: Arg_0 {O(n)}

  3: evalaaron2bb6in->evalaaron2returnin, Arg_1: max([Arg_2, max([Arg_2, Arg_0])+max([0, (2+Arg_1+Arg_0-Arg_2)*max([1, 1+Arg_0])])]) {O(n^2)}

  3: evalaaron2bb6in->evalaaron2returnin, Arg_2: max([Arg_0, max([Arg_1, max([Arg_0, max([Arg_1, Arg_0])])])]) {O(n)}

  4: evalaaron2bb6in->evalaaron2returnin, Arg_0: -1 {O(1)}

  4: evalaaron2bb6in->evalaaron2returnin, Arg_1: max([Arg_2, Arg_0])+max([0, (2+Arg_1+Arg_0-Arg_2)*max([1, 1+Arg_0])]) {O(n^2)}

  4: evalaaron2bb6in->evalaaron2returnin, Arg_2: max([Arg_0, max([Arg_1, Arg_0])]) {O(n)}

  5: evalaaron2bb6in->evalaaron2bb3in, Arg_0: Arg_0 {O(n)}

  5: evalaaron2bb6in->evalaaron2bb3in, Arg_1: max([Arg_2, Arg_0])+max([0, (2+Arg_1+Arg_0-Arg_2)*max([1, 1+Arg_0])]) {O(n^2)}

  5: evalaaron2bb6in->evalaaron2bb3in, Arg_2: max([Arg_0, max([Arg_1, Arg_0])]) {O(n)}

  1: evalaaron2entryin->evalaaron2bb6in, Arg_0: Arg_0 {O(n)}

  1: evalaaron2entryin->evalaaron2bb6in, Arg_1: Arg_2 {O(n)}

  1: evalaaron2entryin->evalaaron2bb6in, Arg_2: Arg_1 {O(n)}

  2: evalaaron2entryin->evalaaron2returnin, Arg_0: -1 {O(1)}

  2: evalaaron2entryin->evalaaron2returnin, Arg_1: Arg_1 {O(n)}

  2: evalaaron2entryin->evalaaron2returnin, Arg_2: Arg_2 {O(n)}

  11: evalaaron2returnin->evalaaron2stop, Arg_0: max([-1, Arg_0]) {O(n)}

  11: evalaaron2returnin->evalaaron2stop, Arg_1: max([Arg_2, max([Arg_1, max([Arg_2, Arg_0])+max([0, (2+Arg_1+Arg_0-Arg_2)*max([1, 1+Arg_0])])])]) {O(n^2)}

  11: evalaaron2returnin->evalaaron2stop, Arg_2: max([Arg_0, max([Arg_1, max([Arg_0, max([Arg_1, max([Arg_0, max([Arg_1, max([Arg_0, max([Arg_2, Arg_0])])])])])])])]) {O(n)}

  0: evalaaron2start->evalaaron2entryin, Arg_0: Arg_0 {O(n)}

  0: evalaaron2start->evalaaron2entryin, Arg_1: Arg_1 {O(n)}

  0: evalaaron2start->evalaaron2entryin, Arg_2: Arg_2 {O(n)}


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

(2)
BOUNDS(1, max(6, 14 + 4 * Arg_0 + 4 * Arg_1 + -4 * Arg_2) + nat(8 + 4 * Arg_0 + 4 * Arg_1 + -4 * Arg_2) + nat(2 + Arg_0 + Arg_1 + -1 * Arg_2))