/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(10 + -1 * Arg_0 + Arg_1, 9)).

(0) CpxIntTrs
(1) Koat2 Proof [FINISHED, 9650 ms]
(2) BOUNDS(1, max(10 + -1 * Arg_0 + Arg_1, 9))


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

(0)
Obligation:
Complexity Int TRS consisting of the following rules:
evalcomplexstart(A, B, C, D, E) -> Com_1(evalcomplexentryin(A, B, C, D, E)) :|: TRUE
evalcomplexentryin(A, B, C, D, E) -> Com_1(evalcomplexbb10in(B, A, C, D, E)) :|: TRUE
evalcomplexbb10in(A, B, C, D, E) -> Com_1(evalcomplexbb8in(A, B, A, B, E)) :|: 29 >= B
evalcomplexbb10in(A, B, C, D, E) -> Com_1(evalcomplexreturnin(A, B, C, D, E)) :|: B >= 30
evalcomplexbb8in(A, B, C, D, E) -> Com_1(evalcomplexbb1in(A, B, C, D, E)) :|: D >= C + 1
evalcomplexbb8in(A, B, C, D, E) -> Com_1(evalcomplexbb9in(A, B, C, D, E)) :|: C >= D
evalcomplexbb1in(A, B, C, D, E) -> Com_1(evalcomplexbb7in(A, B, C, D, C + 7)) :|: C >= 6 && 2 >= C
evalcomplexbb1in(A, B, C, D, E) -> Com_1(evalcomplexbb7in(A, B, C, D, C + 7)) :|: C >= 6
evalcomplexbb1in(A, B, C, D, E) -> Com_1(evalcomplexbb6in(A, B, C, D, C + 7)) :|: C >= 6 && C >= 3 && 5 >= C
evalcomplexbb1in(A, B, C, D, E) -> Com_1(evalcomplexbb7in(A, B, C, D, C + 2)) :|: 5 >= C && 7 >= C
evalcomplexbb1in(A, B, C, D, E) -> Com_1(evalcomplexbb7in(A, B, C, D, C + 2)) :|: 5 >= C && C >= 11
evalcomplexbb1in(A, B, C, D, E) -> Com_1(evalcomplexbb6in(A, B, C, D, C + 2)) :|: 5 >= C && C >= 8 && 10 >= C
evalcomplexbb7in(A, B, C, D, E) -> Com_1(evalcomplexbb8in(A, B, E, D + 1, E)) :|: TRUE
evalcomplexbb6in(A, B, C, D, E) -> Com_1(evalcomplexbb8in(A, B, E, D + 10, E)) :|: TRUE
evalcomplexbb9in(A, B, C, D, E) -> Com_1(evalcomplexbb10in(C - 10, D + 2, C, D, E)) :|: TRUE
evalcomplexreturnin(A, B, C, D, E) -> Com_1(evalcomplexstop(A, B, C, D, E)) :|: TRUE

The start-symbols are:[evalcomplexstart_5]


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

(1) Koat2 Proof (FINISHED)
YES( ?, max([9, 10+Arg_1-Arg_0]) {O(n)})



Initial Complexity Problem:

  Start:  evalcomplexstart  

  Program_Vars:  Arg_0, Arg_1, Arg_2, Arg_3, Arg_4  

  Temp_Vars:  Arg2_P, Arg4_P  

  Locations:  evalcomplexbb10in, evalcomplexbb1in, evalcomplexbb6in, evalcomplexbb8in, evalcomplexbb9in, evalcomplexentryin, evalcomplexreturnin, evalcomplexstart, evalcomplexstop, n_evalcomplexbb1in___1, n_evalcomplexbb1in___3, n_evalcomplexbb8in___2  

  Transitions:

  1292: evalcomplexbb10in->evalcomplexbb10in

  3: evalcomplexbb10in->evalcomplexreturnin

  8: evalcomplexbb1in->evalcomplexbb6in

  11: evalcomplexbb1in->evalcomplexbb6in

  13: evalcomplexbb6in->evalcomplexbb8in

  1316: evalcomplexbb8in->n_evalcomplexbb1in___3

  1: evalcomplexentryin->evalcomplexbb10in

  15: evalcomplexreturnin->evalcomplexstop

  0: evalcomplexstart->evalcomplexentryin

  1312: n_evalcomplexbb1in___1->n_evalcomplexbb8in___2

  1314: n_evalcomplexbb1in___3->evalcomplexbb8in

  1313: n_evalcomplexbb1in___3->n_evalcomplexbb8in___2

  1330: n_evalcomplexbb8in___2->evalcomplexbb9in

  1315: n_evalcomplexbb8in___2->n_evalcomplexbb1in___1  



Timebounds: 

  Overall timebound: max([9, 10+Arg_1-Arg_0]) {O(n)}

  3: evalcomplexbb10in->evalcomplexreturnin: 1 {O(1)}

  1292: evalcomplexbb10in->evalcomplexbb10in: max([0, 1+Arg_1-Arg_0]) {O(n)}

  8: evalcomplexbb1in->evalcomplexbb6in: 1 {O(1)}

  11: evalcomplexbb1in->evalcomplexbb6in: 1 {O(1)}

  13: evalcomplexbb6in->evalcomplexbb8in: 1 {O(1)}

  1316: evalcomplexbb8in->n_evalcomplexbb1in___3: 0 {O(1)}

  1: evalcomplexentryin->evalcomplexbb10in: 1 {O(1)}

  15: evalcomplexreturnin->evalcomplexstop: 1 {O(1)}

  0: evalcomplexstart->evalcomplexentryin: 1 {O(1)}

  1312: n_evalcomplexbb1in___1->n_evalcomplexbb8in___2: 0 {O(1)}

  1313: n_evalcomplexbb1in___3->n_evalcomplexbb8in___2: 1 {O(1)}

  1314: n_evalcomplexbb1in___3->evalcomplexbb8in: 0 {O(1)}

  1315: n_evalcomplexbb8in___2->n_evalcomplexbb1in___1: 0 {O(1)}

  1330: n_evalcomplexbb8in___2->evalcomplexbb9in: 1 {O(1)}



Costbounds:

  Overall costbound: 10+3*max([0, 1+Arg_1-Arg_0]) {O(n)}

  3: evalcomplexbb10in->evalcomplexreturnin: 1 {O(1)}

  1292: evalcomplexbb10in->evalcomplexbb10in: 3*max([0, 1+Arg_1-Arg_0]) {O(n)}

  8: evalcomplexbb1in->evalcomplexbb6in: 1 {O(1)}

  11: evalcomplexbb1in->evalcomplexbb6in: 1 {O(1)}

  13: evalcomplexbb6in->evalcomplexbb8in: 1 {O(1)}

  1316: evalcomplexbb8in->n_evalcomplexbb1in___3: 0 {O(1)}

  1: evalcomplexentryin->evalcomplexbb10in: 1 {O(1)}

  15: evalcomplexreturnin->evalcomplexstop: 1 {O(1)}

  0: evalcomplexstart->evalcomplexentryin: 1 {O(1)}

  1312: n_evalcomplexbb1in___1->n_evalcomplexbb8in___2: 0 {O(1)}

  1313: n_evalcomplexbb1in___3->n_evalcomplexbb8in___2: 2 {O(1)}

  1314: n_evalcomplexbb1in___3->evalcomplexbb8in: 0 {O(1)}

  1315: n_evalcomplexbb8in___2->n_evalcomplexbb1in___1: 0 {O(1)}

  1330: n_evalcomplexbb8in___2->evalcomplexbb9in: 1 {O(1)}



Sizebounds:

`Lower:

  3: evalcomplexbb10in->evalcomplexreturnin, Arg_0: min([Arg_1, -(-(Arg_1)+max([0, 10*(1+Arg_1-Arg_0)]))]) {O(n)}

  3: evalcomplexbb10in->evalcomplexreturnin, Arg_1: 30 {O(1)}

  3: evalcomplexbb10in->evalcomplexreturnin, Arg_2: min([Arg_2, min([Arg_1, -(-(Arg_1)+max([0, 10*(1+Arg_1-Arg_0)]))])]) {O(n)}

  3: evalcomplexbb10in->evalcomplexreturnin, Arg_3: min([Arg_3, Arg_0]) {O(n)}

  3: evalcomplexbb10in->evalcomplexreturnin, Arg_4: Arg_4 {O(n)}

  1292: evalcomplexbb10in->evalcomplexbb10in, Arg_0: Arg_1-max([0, 10*(1+Arg_1-Arg_0)]) {O(n)}

  1292: evalcomplexbb10in->evalcomplexbb10in, Arg_1: Arg_0 {O(n)}

  1292: evalcomplexbb10in->evalcomplexbb10in, Arg_2: min([Arg_1, -(-(Arg_1)+max([0, 10*(1+Arg_1-Arg_0)]))]) {O(n)}

  1292: evalcomplexbb10in->evalcomplexbb10in, Arg_3: Arg_0 {O(n)}

  1292: evalcomplexbb10in->evalcomplexbb10in, Arg_4: Arg_4 {O(n)}

  8: evalcomplexbb1in->evalcomplexbb6in, Arg_0: inf {Infinity}

  8: evalcomplexbb1in->evalcomplexbb6in, Arg_1: inf {Infinity}

  8: evalcomplexbb1in->evalcomplexbb6in, Arg_2: inf {Infinity}

  8: evalcomplexbb1in->evalcomplexbb6in, Arg_3: inf {Infinity}

  8: evalcomplexbb1in->evalcomplexbb6in, Arg_4: inf {Infinity}

  11: evalcomplexbb1in->evalcomplexbb6in, Arg_0: inf {Infinity}

  11: evalcomplexbb1in->evalcomplexbb6in, Arg_1: inf {Infinity}

  11: evalcomplexbb1in->evalcomplexbb6in, Arg_2: inf {Infinity}

  11: evalcomplexbb1in->evalcomplexbb6in, Arg_3: inf {Infinity}

  11: evalcomplexbb1in->evalcomplexbb6in, Arg_4: inf {Infinity}

  13: evalcomplexbb6in->evalcomplexbb8in, Arg_0: inf {Infinity}

  13: evalcomplexbb6in->evalcomplexbb8in, Arg_1: inf {Infinity}

  13: evalcomplexbb6in->evalcomplexbb8in, Arg_2: inf {Infinity}

  13: evalcomplexbb6in->evalcomplexbb8in, Arg_3: inf {Infinity}

  13: evalcomplexbb6in->evalcomplexbb8in, Arg_4: inf {Infinity}

  1316: evalcomplexbb8in->n_evalcomplexbb1in___3, Arg_0: inf {Infinity}

  1316: evalcomplexbb8in->n_evalcomplexbb1in___3, Arg_1: inf {Infinity}

  1316: evalcomplexbb8in->n_evalcomplexbb1in___3, Arg_3: inf {Infinity}

  1: evalcomplexentryin->evalcomplexbb10in, Arg_0: Arg_1 {O(n)}

  1: evalcomplexentryin->evalcomplexbb10in, Arg_1: Arg_0 {O(n)}

  1: evalcomplexentryin->evalcomplexbb10in, Arg_2: Arg_2 {O(n)}

  1: evalcomplexentryin->evalcomplexbb10in, Arg_3: Arg_3 {O(n)}

  1: evalcomplexentryin->evalcomplexbb10in, Arg_4: Arg_4 {O(n)}

  15: evalcomplexreturnin->evalcomplexstop, Arg_0: min([Arg_1, -(-(Arg_1)+max([0, 10*(1+Arg_1-Arg_0)]))]) {O(n)}

  15: evalcomplexreturnin->evalcomplexstop, Arg_1: 30 {O(1)}

  15: evalcomplexreturnin->evalcomplexstop, Arg_2: min([Arg_2, min([Arg_1, -(-(Arg_1)+max([0, 10*(1+Arg_1-Arg_0)]))])]) {O(n)}

  15: evalcomplexreturnin->evalcomplexstop, Arg_3: min([Arg_3, Arg_0]) {O(n)}

  15: evalcomplexreturnin->evalcomplexstop, Arg_4: Arg_4 {O(n)}

  0: evalcomplexstart->evalcomplexentryin, Arg_0: Arg_0 {O(n)}

  0: evalcomplexstart->evalcomplexentryin, Arg_1: Arg_1 {O(n)}

  0: evalcomplexstart->evalcomplexentryin, Arg_2: Arg_2 {O(n)}

  0: evalcomplexstart->evalcomplexentryin, Arg_3: Arg_3 {O(n)}

  0: evalcomplexstart->evalcomplexentryin, Arg_4: Arg_4 {O(n)}

  1312: n_evalcomplexbb1in___1->n_evalcomplexbb8in___2, Arg_0: inf {Infinity}

  1312: n_evalcomplexbb1in___1->n_evalcomplexbb8in___2, Arg_1: inf {Infinity}

  1312: n_evalcomplexbb1in___1->n_evalcomplexbb8in___2, Arg_2: 13 {O(1)}

  1312: n_evalcomplexbb1in___1->n_evalcomplexbb8in___2, Arg_3: 8 {O(1)}

  1312: n_evalcomplexbb1in___1->n_evalcomplexbb8in___2, Arg_4: 13 {O(1)}

  1313: n_evalcomplexbb1in___3->n_evalcomplexbb8in___2, Arg_0: inf {Infinity}

  1313: n_evalcomplexbb1in___3->n_evalcomplexbb8in___2, Arg_1: inf {Infinity}

  1313: n_evalcomplexbb1in___3->n_evalcomplexbb8in___2, Arg_2: 13 {O(1)}

  1313: n_evalcomplexbb1in___3->n_evalcomplexbb8in___2, Arg_3: 8 {O(1)}

  1313: n_evalcomplexbb1in___3->n_evalcomplexbb8in___2, Arg_4: 13 {O(1)}

  1314: n_evalcomplexbb1in___3->evalcomplexbb8in, Arg_0: inf {Infinity}

  1314: n_evalcomplexbb1in___3->evalcomplexbb8in, Arg_1: inf {Infinity}

  1314: n_evalcomplexbb1in___3->evalcomplexbb8in, Arg_3: inf {Infinity}

  1315: n_evalcomplexbb8in___2->n_evalcomplexbb1in___1, Arg_0: inf {Infinity}

  1315: n_evalcomplexbb8in___2->n_evalcomplexbb1in___1, Arg_1: inf {Infinity}

  1315: n_evalcomplexbb8in___2->n_evalcomplexbb1in___1, Arg_2: 6 {O(1)}

  1315: n_evalcomplexbb8in___2->n_evalcomplexbb1in___1, Arg_3: 7 {O(1)}

  1315: n_evalcomplexbb8in___2->n_evalcomplexbb1in___1, Arg_4: 13 {O(1)}

  1330: n_evalcomplexbb8in___2->evalcomplexbb9in, Arg_0: inf {Infinity}

  1330: n_evalcomplexbb8in___2->evalcomplexbb9in, Arg_1: inf {Infinity}

  1330: n_evalcomplexbb8in___2->evalcomplexbb9in, Arg_2: 13 {O(1)}

  1330: n_evalcomplexbb8in___2->evalcomplexbb9in, Arg_3: 8 {O(1)}

  1330: n_evalcomplexbb8in___2->evalcomplexbb9in, Arg_4: 13 {O(1)}

`Upper:

  3: evalcomplexbb10in->evalcomplexreturnin, Arg_0: Arg_1 {O(n)}

  3: evalcomplexbb10in->evalcomplexreturnin, Arg_1: max([31, Arg_0]) {O(n)}

  3: evalcomplexbb10in->evalcomplexreturnin, Arg_2: max([Arg_2, Arg_1]) {O(n)}

  3: evalcomplexbb10in->evalcomplexreturnin, Arg_3: max([29, Arg_3]) {O(n)}

  3: evalcomplexbb10in->evalcomplexreturnin, Arg_4: Arg_4 {O(n)}

  1292: evalcomplexbb10in->evalcomplexbb10in, Arg_0: Arg_1 {O(n)}

  1292: evalcomplexbb10in->evalcomplexbb10in, Arg_1: 31 {O(1)}

  1292: evalcomplexbb10in->evalcomplexbb10in, Arg_2: Arg_1 {O(n)}

  1292: evalcomplexbb10in->evalcomplexbb10in, Arg_3: 29 {O(1)}

  1292: evalcomplexbb10in->evalcomplexbb10in, Arg_4: Arg_4 {O(n)}

  8: evalcomplexbb1in->evalcomplexbb6in, Arg_0: -(inf) {Infinity}

  8: evalcomplexbb1in->evalcomplexbb6in, Arg_1: -(inf) {Infinity}

  8: evalcomplexbb1in->evalcomplexbb6in, Arg_2: -(inf) {Infinity}

  8: evalcomplexbb1in->evalcomplexbb6in, Arg_3: -(inf) {Infinity}

  8: evalcomplexbb1in->evalcomplexbb6in, Arg_4: -(inf) {Infinity}

  11: evalcomplexbb1in->evalcomplexbb6in, Arg_0: -(inf) {Infinity}

  11: evalcomplexbb1in->evalcomplexbb6in, Arg_1: -(inf) {Infinity}

  11: evalcomplexbb1in->evalcomplexbb6in, Arg_2: -(inf) {Infinity}

  11: evalcomplexbb1in->evalcomplexbb6in, Arg_3: -(inf) {Infinity}

  11: evalcomplexbb1in->evalcomplexbb6in, Arg_4: -(inf) {Infinity}

  13: evalcomplexbb6in->evalcomplexbb8in, Arg_0: -(inf) {Infinity}

  13: evalcomplexbb6in->evalcomplexbb8in, Arg_1: -(inf) {Infinity}

  13: evalcomplexbb6in->evalcomplexbb8in, Arg_2: -(inf) {Infinity}

  13: evalcomplexbb6in->evalcomplexbb8in, Arg_3: -(inf) {Infinity}

  13: evalcomplexbb6in->evalcomplexbb8in, Arg_4: -(inf) {Infinity}

  1316: evalcomplexbb8in->n_evalcomplexbb1in___3, Arg_0: -(inf) {Infinity}

  1316: evalcomplexbb8in->n_evalcomplexbb1in___3, Arg_1: -(inf) {Infinity}

  1316: evalcomplexbb8in->n_evalcomplexbb1in___3, Arg_2: 7 {O(1)}

  1316: evalcomplexbb8in->n_evalcomplexbb1in___3, Arg_3: -(inf) {Infinity}

  1316: evalcomplexbb8in->n_evalcomplexbb1in___3, Arg_4: 7 {O(1)}

  1: evalcomplexentryin->evalcomplexbb10in, Arg_0: Arg_1 {O(n)}

  1: evalcomplexentryin->evalcomplexbb10in, Arg_1: Arg_0 {O(n)}

  1: evalcomplexentryin->evalcomplexbb10in, Arg_2: Arg_2 {O(n)}

  1: evalcomplexentryin->evalcomplexbb10in, Arg_3: Arg_3 {O(n)}

  1: evalcomplexentryin->evalcomplexbb10in, Arg_4: Arg_4 {O(n)}

  15: evalcomplexreturnin->evalcomplexstop, Arg_0: Arg_1 {O(n)}

  15: evalcomplexreturnin->evalcomplexstop, Arg_1: max([31, Arg_0]) {O(n)}

  15: evalcomplexreturnin->evalcomplexstop, Arg_2: max([Arg_2, Arg_1]) {O(n)}

  15: evalcomplexreturnin->evalcomplexstop, Arg_3: max([29, Arg_3]) {O(n)}

  15: evalcomplexreturnin->evalcomplexstop, Arg_4: Arg_4 {O(n)}

  0: evalcomplexstart->evalcomplexentryin, Arg_0: Arg_0 {O(n)}

  0: evalcomplexstart->evalcomplexentryin, Arg_1: Arg_1 {O(n)}

  0: evalcomplexstart->evalcomplexentryin, Arg_2: Arg_2 {O(n)}

  0: evalcomplexstart->evalcomplexentryin, Arg_3: Arg_3 {O(n)}

  0: evalcomplexstart->evalcomplexentryin, Arg_4: Arg_4 {O(n)}

  1312: n_evalcomplexbb1in___1->n_evalcomplexbb8in___2, Arg_0: -(inf) {Infinity}

  1312: n_evalcomplexbb1in___1->n_evalcomplexbb8in___2, Arg_1: -(inf) {Infinity}

  1312: n_evalcomplexbb1in___1->n_evalcomplexbb8in___2, Arg_3: -(inf) {Infinity}

  1313: n_evalcomplexbb1in___3->n_evalcomplexbb8in___2, Arg_0: -(inf) {Infinity}

  1313: n_evalcomplexbb1in___3->n_evalcomplexbb8in___2, Arg_1: -(inf) {Infinity}

  1313: n_evalcomplexbb1in___3->n_evalcomplexbb8in___2, Arg_3: -(inf) {Infinity}

  1314: n_evalcomplexbb1in___3->evalcomplexbb8in, Arg_0: -(inf) {Infinity}

  1314: n_evalcomplexbb1in___3->evalcomplexbb8in, Arg_1: -(inf) {Infinity}

  1314: n_evalcomplexbb1in___3->evalcomplexbb8in, Arg_2: 7 {O(1)}

  1314: n_evalcomplexbb1in___3->evalcomplexbb8in, Arg_3: -(inf) {Infinity}

  1314: n_evalcomplexbb1in___3->evalcomplexbb8in, Arg_4: 7 {O(1)}

  1315: n_evalcomplexbb8in___2->n_evalcomplexbb1in___1, Arg_0: -(inf) {Infinity}

  1315: n_evalcomplexbb8in___2->n_evalcomplexbb1in___1, Arg_1: -(inf) {Infinity}

  1315: n_evalcomplexbb8in___2->n_evalcomplexbb1in___1, Arg_3: -(inf) {Infinity}

  1330: n_evalcomplexbb8in___2->evalcomplexbb9in, Arg_0: -(inf) {Infinity}

  1330: n_evalcomplexbb8in___2->evalcomplexbb9in, Arg_1: -(inf) {Infinity}

  1330: n_evalcomplexbb8in___2->evalcomplexbb9in, Arg_3: -(inf) {Infinity}


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

(2)
BOUNDS(1, max(10 + -1 * Arg_0 + Arg_1, 9))