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


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


WORST_CASE(?, O(n^2))
proof of /export/starexec/sandbox/benchmark/theBenchmark.koat
# AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty


The runtime complexity of the given CpxIntTrs could be proven to be BOUNDS(1, max(1, 1 + 3 * Arg_0) + nat(2 + 2 * Arg_0) + nat(3 * Arg_0 * max(1, Arg_0)) + nat(3 * Arg_0 * max(6, 3 * Arg_0)) + nat(Arg_0) + max(1, 1 + 2 * Arg_0) + max(5 + 6 * Arg_0, 5)).

(0) CpxIntTrs
(1) Koat2 Proof [FINISHED, 931 ms]
(2) BOUNDS(1, max(1, 1 + 3 * Arg_0) + nat(2 + 2 * Arg_0) + nat(3 * Arg_0 * max(1, Arg_0)) + nat(3 * Arg_0 * max(6, 3 * Arg_0)) + nat(Arg_0) + max(1, 1 + 2 * Arg_0) + max(5 + 6 * Arg_0, 5))


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

(0)
Obligation:
Complexity Int TRS consisting of the following rules:
evalloopsstart(A, B) -> Com_1(evalloopsentryin(A, B)) :|: TRUE
evalloopsentryin(A, B) -> Com_1(evalloopsbb6in(A, B)) :|: A >= 0
evalloopsentryin(A, B) -> Com_1(evalloopsreturnin(A, B)) :|: 0 >= A + 1
evalloopsbb6in(A, B) -> Com_1(evalloopsbb1in(A, B)) :|: A >= 0
evalloopsbb6in(A, B) -> Com_1(evalloopsreturnin(A, B)) :|: 0 >= A + 1
evalloopsbb1in(A, B) -> Com_1(evalloopsbb4in(A, 1)) :|: A >= 2
evalloopsbb1in(A, B) -> Com_1(evalloopsbb5in(A, C)) :|: 1 >= A
evalloopsbb4in(A, B) -> Com_1(evalloopsbb3in(A, B)) :|: A >= B + 1
evalloopsbb4in(A, B) -> Com_1(evalloopsbb5in(A, B)) :|: B >= A
evalloopsbb3in(A, B) -> Com_1(evalloopsbb4in(A, 2 * B)) :|: TRUE
evalloopsbb5in(A, B) -> Com_1(evalloopsbb6in(A - 1, B)) :|: TRUE
evalloopsreturnin(A, B) -> Com_1(evalloopsstop(A, B)) :|: TRUE

The start-symbols are:[evalloopsstart_2]


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

(1) Koat2 Proof (FINISHED)
YES( ?, 5+2*max([0, 3*Arg_0])+max([1, 1+3*Arg_0])+max([0, 1+Arg_0])+max([0, 1+Arg_0])+max([0, 3*Arg_0*max([1, Arg_0])])+max([0, 3*Arg_0*max([6, 3*max([1, Arg_0])])])+max([0, Arg_0])+max([1, 1+2*Arg_0]) {O(n^2)})



Initial Complexity Problem:

  Start:  evalloopsstart  

  Program_Vars:  Arg_0, Arg_1  

  Temp_Vars:  C  

  Locations:  evalloopsbb1in, evalloopsbb3in, evalloopsbb4in, evalloopsbb5in, evalloopsbb6in, evalloopsentryin, evalloopsreturnin, evalloopsstart, evalloopsstop  

  Transitions:

  evalloopsbb1in(Arg_0,Arg_1) -> evalloopsbb4in(Arg_0,1):|:0 <= Arg_0 && 2 <= Arg_0

  evalloopsbb1in(Arg_0,Arg_1) -> evalloopsbb5in(Arg_0,C):|:0 <= Arg_0 && Arg_0 <= 1

  evalloopsbb3in(Arg_0,Arg_1) -> evalloopsbb4in(Arg_0,(2)*Arg_1):|:1+Arg_1 <= Arg_0 && 1 <= Arg_1 && 3 <= Arg_0+Arg_1 && 2 <= Arg_0

  evalloopsbb4in(Arg_0,Arg_1) -> evalloopsbb3in(Arg_0,Arg_1):|:1 <= Arg_1 && 3 <= Arg_0+Arg_1 && 2 <= Arg_0 && Arg_1+1 <= Arg_0

  evalloopsbb4in(Arg_0,Arg_1) -> evalloopsbb5in(Arg_0,Arg_1):|:1 <= Arg_1 && 3 <= Arg_0+Arg_1 && 2 <= Arg_0 && Arg_0 <= Arg_1

  evalloopsbb5in(Arg_0,Arg_1) -> evalloopsbb6in(Arg_0-1,Arg_1):|:0 <= Arg_0

  evalloopsbb6in(Arg_0,Arg_1) -> evalloopsbb1in(Arg_0,Arg_1):|:0 <= Arg_0

  evalloopsbb6in(Arg_0,Arg_1) -> evalloopsreturnin(Arg_0,Arg_1):|:Arg_0+1 <= 0

  evalloopsentryin(Arg_0,Arg_1) -> evalloopsbb6in(Arg_0,Arg_1):|:0 <= Arg_0

  evalloopsentryin(Arg_0,Arg_1) -> evalloopsreturnin(Arg_0,Arg_1):|:Arg_0+1 <= 0

  evalloopsreturnin(Arg_0,Arg_1) -> evalloopsstop(Arg_0,Arg_1):|:1+Arg_0 <= 0

  evalloopsstart(Arg_0,Arg_1) -> evalloopsentryin(Arg_0,Arg_1):|:  



Timebounds: 

  Overall timebound: 5+2*max([0, 3*Arg_0])+max([1, 1+3*Arg_0])+max([0, 1+Arg_0])+max([0, 1+Arg_0])+max([0, 3*Arg_0*max([1, Arg_0])])+max([0, 3*Arg_0*max([6, 3*max([1, Arg_0])])])+max([0, Arg_0])+max([1, 1+2*Arg_0]) {O(n^2)}

  5: evalloopsbb1in->evalloopsbb4in: max([0, 1+Arg_0]) {O(n)}

  6: evalloopsbb1in->evalloopsbb5in: max([1, 1+2*Arg_0]) {O(n)}

  9: evalloopsbb3in->evalloopsbb4in: max([0, 3*Arg_0*max([1, Arg_0])])+max([0, Arg_0]) {O(n^2)}

  7: evalloopsbb4in->evalloopsbb3in: max([0, 3*Arg_0*max([6, 3*max([1, Arg_0])])])+max([0, 3*Arg_0]) {O(n^2)}

  8: evalloopsbb4in->evalloopsbb5in: max([0, 3*Arg_0]) {O(n)}

  10: evalloopsbb5in->evalloopsbb6in: max([0, 1+Arg_0]) {O(n)}

  3: evalloopsbb6in->evalloopsbb1in: max([1, 1+3*Arg_0]) {O(n)}

  4: evalloopsbb6in->evalloopsreturnin: 1 {O(1)}

  1: evalloopsentryin->evalloopsbb6in: 1 {O(1)}

  2: evalloopsentryin->evalloopsreturnin: 1 {O(1)}

  11: evalloopsreturnin->evalloopsstop: 1 {O(1)}

  0: evalloopsstart->evalloopsentryin: 1 {O(1)}



Costbounds:

  Overall costbound: 5+2*max([0, 3*Arg_0])+max([1, 1+3*Arg_0])+max([0, 1+Arg_0])+max([0, 1+Arg_0])+max([0, 3*Arg_0*max([1, Arg_0])])+max([0, 3*Arg_0*max([6, 3*max([1, Arg_0])])])+max([0, Arg_0])+max([1, 1+2*Arg_0]) {O(n^2)}

  5: evalloopsbb1in->evalloopsbb4in: max([0, 1+Arg_0]) {O(n)}

  6: evalloopsbb1in->evalloopsbb5in: max([1, 1+2*Arg_0]) {O(n)}

  9: evalloopsbb3in->evalloopsbb4in: max([0, 3*Arg_0*max([1, Arg_0])])+max([0, Arg_0]) {O(n^2)}

  7: evalloopsbb4in->evalloopsbb3in: max([0, 3*Arg_0*max([6, 3*max([1, Arg_0])])])+max([0, 3*Arg_0]) {O(n^2)}

  8: evalloopsbb4in->evalloopsbb5in: max([0, 3*Arg_0]) {O(n)}

  10: evalloopsbb5in->evalloopsbb6in: max([0, 1+Arg_0]) {O(n)}

  3: evalloopsbb6in->evalloopsbb1in: max([1, 1+3*Arg_0]) {O(n)}

  4: evalloopsbb6in->evalloopsreturnin: 1 {O(1)}

  1: evalloopsentryin->evalloopsbb6in: 1 {O(1)}

  2: evalloopsentryin->evalloopsreturnin: 1 {O(1)}

  11: evalloopsreturnin->evalloopsstop: 1 {O(1)}

  0: evalloopsstart->evalloopsentryin: 1 {O(1)}



Sizebounds:

`Lower:

  5: evalloopsbb1in->evalloopsbb4in, Arg_0: 2 {O(1)}

  5: evalloopsbb1in->evalloopsbb4in, Arg_1: 1 {O(1)}

  6: evalloopsbb1in->evalloopsbb5in, Arg_0: 0 {O(1)}

  9: evalloopsbb3in->evalloopsbb4in, Arg_0: 2 {O(1)}

  9: evalloopsbb3in->evalloopsbb4in, Arg_1: 2 {O(1)}

  7: evalloopsbb4in->evalloopsbb3in, Arg_0: 2 {O(1)}

  7: evalloopsbb4in->evalloopsbb3in, Arg_1: 1 {O(1)}

  8: evalloopsbb4in->evalloopsbb5in, Arg_0: 2 {O(1)}

  8: evalloopsbb4in->evalloopsbb5in, Arg_1: 2 {O(1)}

  10: evalloopsbb5in->evalloopsbb6in, Arg_0: -1 {O(1)}

  3: evalloopsbb6in->evalloopsbb1in, Arg_0: 0 {O(1)}

  4: evalloopsbb6in->evalloopsreturnin, Arg_0: -1 {O(1)}

  1: evalloopsentryin->evalloopsbb6in, Arg_0: 0 {O(1)}

  1: evalloopsentryin->evalloopsbb6in, Arg_1: Arg_1 {O(n)}

  2: evalloopsentryin->evalloopsreturnin, Arg_0: Arg_0 {O(n)}

  2: evalloopsentryin->evalloopsreturnin, Arg_1: Arg_1 {O(n)}

  11: evalloopsreturnin->evalloopsstop, Arg_0: min([-1, Arg_0]) {O(n)}

  0: evalloopsstart->evalloopsentryin, Arg_0: Arg_0 {O(n)}

  0: evalloopsstart->evalloopsentryin, Arg_1: Arg_1 {O(n)}

`Upper:

  5: evalloopsbb1in->evalloopsbb4in, Arg_0: max([1, Arg_0]) {O(n)}

  5: evalloopsbb1in->evalloopsbb4in, Arg_1: 1 {O(1)}

  6: evalloopsbb1in->evalloopsbb5in, Arg_0: 1 {O(1)}

  9: evalloopsbb3in->evalloopsbb4in, Arg_0: max([1, Arg_0]) {O(n)}

  9: evalloopsbb3in->evalloopsbb4in, Arg_1: 2^(max([0, 3*Arg_0*max([1, Arg_0])])+max([0, Arg_0])) {O(EXP)}

  7: evalloopsbb4in->evalloopsbb3in, Arg_0: max([1, Arg_0]) {O(n)}

  7: evalloopsbb4in->evalloopsbb3in, Arg_1: 2^(max([0, 3*Arg_0*max([1, Arg_0])])+max([0, Arg_0])) {O(EXP)}

  8: evalloopsbb4in->evalloopsbb5in, Arg_0: max([1, Arg_0]) {O(n)}

  8: evalloopsbb4in->evalloopsbb5in, Arg_1: 2^(max([0, 3*Arg_0*max([1, Arg_0])])+max([0, Arg_0])) {O(EXP)}

  10: evalloopsbb5in->evalloopsbb6in, Arg_0: max([1, Arg_0]) {O(n)}

  3: evalloopsbb6in->evalloopsbb1in, Arg_0: max([1, Arg_0]) {O(n)}

  4: evalloopsbb6in->evalloopsreturnin, Arg_0: -1 {O(1)}

  1: evalloopsentryin->evalloopsbb6in, Arg_0: Arg_0 {O(n)}

  1: evalloopsentryin->evalloopsbb6in, Arg_1: Arg_1 {O(n)}

  2: evalloopsentryin->evalloopsreturnin, Arg_0: -1 {O(1)}

  2: evalloopsentryin->evalloopsreturnin, Arg_1: Arg_1 {O(n)}

  11: evalloopsreturnin->evalloopsstop, Arg_0: -1 {O(1)}

  0: evalloopsstart->evalloopsentryin, Arg_0: Arg_0 {O(n)}

  0: evalloopsstart->evalloopsentryin, Arg_1: Arg_1 {O(n)}


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

(2)
BOUNDS(1, max(1, 1 + 3 * Arg_0) + nat(2 + 2 * Arg_0) + nat(3 * Arg_0 * max(1, Arg_0)) + nat(3 * Arg_0 * max(6, 3 * Arg_0)) + nat(Arg_0) + max(1, 1 + 2 * Arg_0) + max(5 + 6 * Arg_0, 5))