/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(256 + -254 * Arg_1, 510) + max(-1 + 254 * Arg_1, 253) + max(-507 + -64516 * Arg_1, 64009) + max(62756 + 193803 * Arg_1, 256559)). (0) CpxIntTrs (1) Koat2 Proof [FINISHED, 5458 ms] (2) BOUNDS(1, max(256 + -254 * Arg_1, 510) + max(-1 + 254 * Arg_1, 253) + max(-507 + -64516 * Arg_1, 64009) + max(62756 + 193803 * Arg_1, 256559)) ---------------------------------------- (0) Obligation: Complexity Int TRS consisting of the following rules: evalfstart(A, B) -> Com_1(evalfentryin(A, B)) :|: TRUE evalfentryin(A, B) -> Com_1(evalfbb3in(B, A)) :|: TRUE evalfbb3in(A, B) -> Com_1(evalfbbin(A, B)) :|: B >= 1 && 254 >= B evalfbb3in(A, B) -> Com_1(evalfreturnin(A, B)) :|: 0 >= B evalfbb3in(A, B) -> Com_1(evalfreturnin(A, B)) :|: B >= 255 evalfbbin(A, B) -> Com_1(evalfbb1in(A, B)) :|: 0 >= A + 1 evalfbbin(A, B) -> Com_1(evalfbb1in(A, B)) :|: A >= 1 evalfbbin(A, B) -> Com_1(evalfbb2in(A, B)) :|: A >= 0 && A <= 0 evalfbb1in(A, B) -> Com_1(evalfbb3in(A, B + 1)) :|: TRUE evalfbb2in(A, B) -> Com_1(evalfbb3in(A, B - 1)) :|: TRUE evalfreturnin(A, B) -> Com_1(evalfstop(A, B)) :|: TRUE The start-symbols are:[evalfstart_2] ---------------------------------------- (1) Koat2 Proof (FINISHED) YES( ?, 257+max([253, -1+-254*Arg_1])+max([253, -1+254*Arg_1])+max([64009, -507+-64516*Arg_1])+max([256559, 62756+193803*Arg_1]) {O(n)}) Initial Complexity Problem: Start: evalfstart Program_Vars: Arg_0, Arg_1 Temp_Vars: Locations: evalfbb3in, evalfentryin, evalfreturnin, evalfstart, evalfstop, n_evalfbb3in___4, n_evalfbb3in___5, n_evalfbb3in___6, n_evalfbbin___1, n_evalfbbin___2, n_evalfbbin___3, n_evalfbbin___7 Transitions: 3: evalfbb3in->evalfreturnin 4: evalfbb3in->evalfreturnin 370: evalfbb3in->n_evalfbbin___7 1: evalfentryin->evalfbb3in 10: evalfreturnin->evalfstop 0: evalfstart->evalfentryin 390: n_evalfbb3in___4->evalfreturnin 393: n_evalfbb3in___4->evalfreturnin 396: n_evalfbb3in___4->evalfreturnin 399: n_evalfbb3in___4->evalfreturnin 367: n_evalfbb3in___4->n_evalfbbin___1 391: n_evalfbb3in___5->evalfreturnin 394: n_evalfbb3in___5->evalfreturnin 397: n_evalfbb3in___5->evalfreturnin 400: n_evalfbb3in___5->evalfreturnin 368: n_evalfbb3in___5->n_evalfbbin___2 392: n_evalfbb3in___6->evalfreturnin 395: n_evalfbb3in___6->evalfreturnin 398: n_evalfbb3in___6->evalfreturnin 401: n_evalfbb3in___6->evalfreturnin 369: n_evalfbb3in___6->n_evalfbbin___3 371: n_evalfbbin___1->n_evalfbb3in___4 372: n_evalfbbin___2->n_evalfbb3in___5 373: n_evalfbbin___3->n_evalfbb3in___6 374: n_evalfbbin___7->n_evalfbb3in___4 375: n_evalfbbin___7->n_evalfbb3in___5 376: n_evalfbbin___7->n_evalfbb3in___6 Timebounds: Overall timebound: 257+max([253, -1+-254*Arg_1])+max([253, -1+254*Arg_1])+max([64009, -507+-64516*Arg_1])+max([256559, 62756+193803*Arg_1]) {O(n)} 3: evalfbb3in->evalfreturnin: 1 {O(1)} 4: evalfbb3in->evalfreturnin: 1 {O(1)} 370: evalfbb3in->n_evalfbbin___7: 1 {O(1)} 1: evalfentryin->evalfbb3in: 1 {O(1)} 10: evalfreturnin->evalfstop: 1 {O(1)} 0: evalfstart->evalfentryin: 1 {O(1)} 367: n_evalfbb3in___4->n_evalfbbin___1: 64263 {O(1)} 390: n_evalfbb3in___4->evalfreturnin: 1 {O(1)} 393: n_evalfbb3in___4->evalfreturnin: 1 {O(1)} 396: n_evalfbb3in___4->evalfreturnin: 1 {O(1)} 399: n_evalfbb3in___4->evalfreturnin: 1 {O(1)} 368: n_evalfbb3in___5->n_evalfbbin___2: max([192278, -1525+193803*Arg_1]) {O(n)} 391: n_evalfbb3in___5->evalfreturnin: 1 {O(1)} 394: n_evalfbb3in___5->evalfreturnin: 1 {O(1)} 397: n_evalfbb3in___5->evalfreturnin: 1 {O(1)} 400: n_evalfbb3in___5->evalfreturnin: 1 {O(1)} 369: n_evalfbb3in___6->n_evalfbbin___3: max([64009, -507+-64516*Arg_1]) {O(n)} 392: n_evalfbb3in___6->evalfreturnin: 1 {O(1)} 395: n_evalfbb3in___6->evalfreturnin: 1 {O(1)} 398: n_evalfbb3in___6->evalfreturnin: 1 {O(1)} 401: n_evalfbb3in___6->evalfreturnin: 1 {O(1)} 371: n_evalfbbin___1->n_evalfbb3in___4: 254 {O(1)} 372: n_evalfbbin___2->n_evalfbb3in___5: max([253, -1+254*Arg_1]) {O(n)} 373: n_evalfbbin___3->n_evalfbb3in___6: max([253, -1+-254*Arg_1]) {O(n)} 374: n_evalfbbin___7->n_evalfbb3in___4: 1 {O(1)} 375: n_evalfbbin___7->n_evalfbb3in___5: 1 {O(1)} 376: n_evalfbbin___7->n_evalfbb3in___6: 1 {O(1)} Costbounds: Overall costbound: 514+2*max([253, -1+-254*Arg_1])+2*max([253, -1+254*Arg_1])+max([256559, 62756+193803*Arg_1])+max([64009, -507+-64516*Arg_1]) {O(n)} 3: evalfbb3in->evalfreturnin: 1 {O(1)} 4: evalfbb3in->evalfreturnin: 1 {O(1)} 370: evalfbb3in->n_evalfbbin___7: 1 {O(1)} 1: evalfentryin->evalfbb3in: 1 {O(1)} 10: evalfreturnin->evalfstop: 1 {O(1)} 0: evalfstart->evalfentryin: 1 {O(1)} 367: n_evalfbb3in___4->n_evalfbbin___1: 64263 {O(1)} 390: n_evalfbb3in___4->evalfreturnin: 1 {O(1)} 393: n_evalfbb3in___4->evalfreturnin: 1 {O(1)} 396: n_evalfbb3in___4->evalfreturnin: 1 {O(1)} 399: n_evalfbb3in___4->evalfreturnin: 1 {O(1)} 368: n_evalfbb3in___5->n_evalfbbin___2: max([192278, -1525+193803*Arg_1]) {O(n)} 391: n_evalfbb3in___5->evalfreturnin: 1 {O(1)} 394: n_evalfbb3in___5->evalfreturnin: 1 {O(1)} 397: n_evalfbb3in___5->evalfreturnin: 1 {O(1)} 400: n_evalfbb3in___5->evalfreturnin: 1 {O(1)} 369: n_evalfbb3in___6->n_evalfbbin___3: max([64009, -507+-64516*Arg_1]) {O(n)} 392: n_evalfbb3in___6->evalfreturnin: 1 {O(1)} 395: n_evalfbb3in___6->evalfreturnin: 1 {O(1)} 398: n_evalfbb3in___6->evalfreturnin: 1 {O(1)} 401: n_evalfbb3in___6->evalfreturnin: 1 {O(1)} 371: n_evalfbbin___1->n_evalfbb3in___4: 508 {O(1)} 372: n_evalfbbin___2->n_evalfbb3in___5: 2*max([253, -1+254*Arg_1]) {O(n)} 373: n_evalfbbin___3->n_evalfbb3in___6: 2*max([253, -1+-254*Arg_1]) {O(n)} 374: n_evalfbbin___7->n_evalfbb3in___4: 2 {O(1)} 375: n_evalfbbin___7->n_evalfbb3in___5: 2 {O(1)} 376: n_evalfbbin___7->n_evalfbb3in___6: 2 {O(1)} Sizebounds: `Lower: 3: evalfbb3in->evalfreturnin, Arg_0: max([Arg_1, max([Arg_1, max([Arg_1, max([Arg_1, max([Arg_1, max([Arg_1, min([0, Arg_1])])])])])])]) {O(n)} 3: evalfbb3in->evalfreturnin, Arg_1: max([Arg_0, max([Arg_0, max([Arg_0, max([Arg_0, max([Arg_0, max([Arg_0, min([0, Arg_0])])])])])])]) {O(n)} 4: evalfbb3in->evalfreturnin, Arg_0: max([Arg_1, max([Arg_1, max([Arg_1, max([Arg_1, max([Arg_1, max([Arg_1, min([0, Arg_1])])])])])])]) {O(n)} 4: evalfbb3in->evalfreturnin, Arg_1: 255 {O(1)} 370: evalfbb3in->n_evalfbbin___7, Arg_0: Arg_1 {O(n)} 370: evalfbb3in->n_evalfbbin___7, Arg_1: 1 {O(1)} 1: evalfentryin->evalfbb3in, Arg_0: Arg_1 {O(n)} 1: evalfentryin->evalfbb3in, Arg_1: Arg_0 {O(n)} 10: evalfreturnin->evalfstop, Arg_0: max([min([0, min([max([Arg_1, max([Arg_1, max([Arg_1, max([Arg_1, max([Arg_1, max([Arg_1, min([0, Arg_1])])])])])])]), min([Arg_1, max([Arg_1, max([Arg_1, max([Arg_1, max([Arg_1, max([Arg_1, max([Arg_1, min([0, Arg_1])])])])])])])])])]), max([min([0, min([max([Arg_1, max([Arg_1, max([Arg_1, max([Arg_1, max([Arg_1, min([0, Arg_1])])])])])]), min([Arg_1, max([Arg_1, max([Arg_1, max([Arg_1, max([Arg_1, max([Arg_1, min([0, Arg_1])])])])])])])])]), max([min([0, min([max([Arg_1, max([Arg_1, max([Arg_1, max([Arg_1, min([0, Arg_1])])])])]), min([Arg_1, max([Arg_1, max([Arg_1, max([Arg_1, max([Arg_1, min([0, Arg_1])])])])])])])]), max([min([0, min([max([Arg_1, max([Arg_1, max([Arg_1, min([0, Arg_1])])])]), min([Arg_1, max([Arg_1, max([Arg_1, max([Arg_1, min([0, Arg_1])])])])])])]), max([min([0, min([max([Arg_1, max([Arg_1, min([0, Arg_1])])]), min([Arg_1, max([Arg_1, max([Arg_1, min([0, Arg_1])])])])])]), max([min([0, min([max([Arg_1, min([0, Arg_1])]), min([Arg_1, max([Arg_1, min([0, Arg_1])])])])]), min([0, Arg_1])])])])])])]) {O(n)} 10: evalfreturnin->evalfstop, Arg_1: max([min([0, max([Arg_0, max([Arg_0, max([Arg_0, max([Arg_0, max([Arg_0, max([Arg_0, min([0, Arg_0])])])])])])])]), max([min([0, max([Arg_0, max([Arg_0, max([Arg_0, max([Arg_0, max([Arg_0, min([0, Arg_0])])])])])])]), max([min([0, max([Arg_0, max([Arg_0, max([Arg_0, max([Arg_0, min([0, Arg_0])])])])])]), max([min([0, max([Arg_0, max([Arg_0, max([Arg_0, min([0, Arg_0])])])])]), max([min([0, max([Arg_0, max([Arg_0, min([0, Arg_0])])])]), max([min([0, max([Arg_0, min([0, Arg_0])])]), min([255, min([0, Arg_0])])])])])])])]) {O(n)} 0: evalfstart->evalfentryin, Arg_0: Arg_0 {O(n)} 0: evalfstart->evalfentryin, Arg_1: Arg_1 {O(n)} 367: n_evalfbb3in___4->n_evalfbbin___1, Arg_0: 0 {O(1)} 367: n_evalfbb3in___4->n_evalfbbin___1, Arg_1: 1 {O(1)} 390: n_evalfbb3in___4->evalfreturnin, Arg_0: 0 {O(1)} 390: n_evalfbb3in___4->evalfreturnin, Arg_1: 0 {O(1)} 393: n_evalfbb3in___4->evalfreturnin, Arg_0: inf {Infinity} 393: n_evalfbb3in___4->evalfreturnin, Arg_1: inf {Infinity} 396: n_evalfbb3in___4->evalfreturnin, Arg_0: 0 {O(1)} 396: n_evalfbb3in___4->evalfreturnin, Arg_1: 0 {O(1)} 399: n_evalfbb3in___4->evalfreturnin, Arg_0: inf {Infinity} 399: n_evalfbb3in___4->evalfreturnin, Arg_1: inf {Infinity} 368: n_evalfbb3in___5->n_evalfbbin___2, Arg_0: 1 {O(1)} 368: n_evalfbb3in___5->n_evalfbbin___2, Arg_1: 1 {O(1)} 391: n_evalfbb3in___5->evalfreturnin, Arg_0: inf {Infinity} 391: n_evalfbb3in___5->evalfreturnin, Arg_1: inf {Infinity} 394: n_evalfbb3in___5->evalfreturnin, Arg_0: 1 {O(1)} 394: n_evalfbb3in___5->evalfreturnin, Arg_1: 255 {O(1)} 397: n_evalfbb3in___5->evalfreturnin, Arg_0: inf {Infinity} 397: n_evalfbb3in___5->evalfreturnin, Arg_1: inf {Infinity} 400: n_evalfbb3in___5->evalfreturnin, Arg_0: 1 {O(1)} 400: n_evalfbb3in___5->evalfreturnin, Arg_1: 255 {O(1)} 369: n_evalfbb3in___6->n_evalfbbin___3, Arg_0: Arg_1 {O(n)} 369: n_evalfbb3in___6->n_evalfbbin___3, Arg_1: 1 {O(1)} 392: n_evalfbb3in___6->evalfreturnin, Arg_0: inf {Infinity} 392: n_evalfbb3in___6->evalfreturnin, Arg_1: inf {Infinity} 395: n_evalfbb3in___6->evalfreturnin, Arg_0: Arg_1 {O(n)} 395: n_evalfbb3in___6->evalfreturnin, Arg_1: 255 {O(1)} 398: n_evalfbb3in___6->evalfreturnin, Arg_0: inf {Infinity} 398: n_evalfbb3in___6->evalfreturnin, Arg_1: inf {Infinity} 401: n_evalfbb3in___6->evalfreturnin, Arg_0: Arg_1 {O(n)} 401: n_evalfbb3in___6->evalfreturnin, Arg_1: 255 {O(1)} 371: n_evalfbbin___1->n_evalfbb3in___4, Arg_0: 0 {O(1)} 371: n_evalfbbin___1->n_evalfbb3in___4, Arg_1: 0 {O(1)} 372: n_evalfbbin___2->n_evalfbb3in___5, Arg_0: 1 {O(1)} 372: n_evalfbbin___2->n_evalfbb3in___5, Arg_1: 2 {O(1)} 373: n_evalfbbin___3->n_evalfbb3in___6, Arg_0: Arg_1 {O(n)} 373: n_evalfbbin___3->n_evalfbb3in___6, Arg_1: 2 {O(1)} 374: n_evalfbbin___7->n_evalfbb3in___4, Arg_0: 0 {O(1)} 374: n_evalfbbin___7->n_evalfbb3in___4, Arg_1: 0 {O(1)} 375: n_evalfbbin___7->n_evalfbb3in___5, Arg_0: 1 {O(1)} 375: n_evalfbbin___7->n_evalfbb3in___5, Arg_1: 2 {O(1)} 376: n_evalfbbin___7->n_evalfbb3in___6, Arg_0: Arg_1 {O(n)} 376: n_evalfbbin___7->n_evalfbb3in___6, Arg_1: 2 {O(1)} `Upper: 3: evalfbb3in->evalfreturnin, Arg_0: min([Arg_1, min([Arg_1, min([Arg_1, min([Arg_1, min([Arg_1, min([Arg_1, max([0, Arg_1])])])])])])]) {O(n)} 3: evalfbb3in->evalfreturnin, Arg_1: 0 {O(1)} 4: evalfbb3in->evalfreturnin, Arg_0: min([Arg_1, min([Arg_1, min([Arg_1, min([Arg_1, min([Arg_1, min([Arg_1, max([0, Arg_1])])])])])])]) {O(n)} 4: evalfbb3in->evalfreturnin, Arg_1: min([Arg_0, min([Arg_0, min([Arg_0, min([Arg_0, min([Arg_0, min([Arg_0, max([255, Arg_0])])])])])])]) {O(n)} 370: evalfbb3in->n_evalfbbin___7, Arg_0: Arg_1 {O(n)} 370: evalfbb3in->n_evalfbbin___7, Arg_1: 254 {O(1)} 1: evalfentryin->evalfbb3in, Arg_0: Arg_1 {O(n)} 1: evalfentryin->evalfbb3in, Arg_1: Arg_0 {O(n)} 10: evalfreturnin->evalfstop, Arg_0: min([max([0, max([Arg_1, min([Arg_1, min([Arg_1, min([Arg_1, min([Arg_1, min([Arg_1, min([Arg_1, max([0, Arg_1])])])])])])])])]), min([max([0, max([Arg_1, min([Arg_1, min([Arg_1, min([Arg_1, min([Arg_1, min([Arg_1, max([0, Arg_1])])])])])])])]), min([max([0, max([Arg_1, min([Arg_1, min([Arg_1, min([Arg_1, min([Arg_1, max([0, Arg_1])])])])])])]), min([max([0, max([Arg_1, min([Arg_1, min([Arg_1, min([Arg_1, max([0, Arg_1])])])])])]), min([max([0, max([Arg_1, min([Arg_1, min([Arg_1, max([0, Arg_1])])])])]), min([max([0, max([Arg_1, min([Arg_1, max([0, Arg_1])])])]), max([0, Arg_1])])])])])])]) {O(n)} 10: evalfreturnin->evalfstop, Arg_1: min([max([255, min([Arg_0, min([Arg_0, min([Arg_0, min([Arg_0, min([Arg_0, min([Arg_0, max([255, Arg_0])])])])])])])]), min([max([255, min([Arg_0, min([Arg_0, min([Arg_0, min([Arg_0, min([Arg_0, max([255, Arg_0])])])])])])]), min([max([255, min([Arg_0, min([Arg_0, min([Arg_0, min([Arg_0, max([255, Arg_0])])])])])]), min([max([255, min([Arg_0, min([Arg_0, min([Arg_0, max([255, Arg_0])])])])]), min([max([255, min([Arg_0, min([Arg_0, max([255, Arg_0])])])]), min([max([255, min([Arg_0, max([255, Arg_0])])]), max([255, Arg_0])])])])])])]) {O(n)} 0: evalfstart->evalfentryin, Arg_0: Arg_0 {O(n)} 0: evalfstart->evalfentryin, Arg_1: Arg_1 {O(n)} 367: n_evalfbb3in___4->n_evalfbbin___1, Arg_0: 0 {O(1)} 367: n_evalfbb3in___4->n_evalfbbin___1, Arg_1: 254 {O(1)} 390: n_evalfbb3in___4->evalfreturnin, Arg_0: 0 {O(1)} 390: n_evalfbb3in___4->evalfreturnin, Arg_1: 0 {O(1)} 393: n_evalfbb3in___4->evalfreturnin, Arg_0: -(inf) {Infinity} 393: n_evalfbb3in___4->evalfreturnin, Arg_1: -(inf) {Infinity} 396: n_evalfbb3in___4->evalfreturnin, Arg_0: 0 {O(1)} 396: n_evalfbb3in___4->evalfreturnin, Arg_1: 0 {O(1)} 399: n_evalfbb3in___4->evalfreturnin, Arg_0: -(inf) {Infinity} 399: n_evalfbb3in___4->evalfreturnin, Arg_1: -(inf) {Infinity} 368: n_evalfbb3in___5->n_evalfbbin___2, Arg_0: Arg_1 {O(n)} 368: n_evalfbb3in___5->n_evalfbbin___2, Arg_1: 254 {O(1)} 391: n_evalfbb3in___5->evalfreturnin, Arg_0: -(inf) {Infinity} 391: n_evalfbb3in___5->evalfreturnin, Arg_1: -(inf) {Infinity} 394: n_evalfbb3in___5->evalfreturnin, Arg_0: Arg_1 {O(n)} 394: n_evalfbb3in___5->evalfreturnin, Arg_1: 255 {O(1)} 397: n_evalfbb3in___5->evalfreturnin, Arg_0: -(inf) {Infinity} 397: n_evalfbb3in___5->evalfreturnin, Arg_1: -(inf) {Infinity} 400: n_evalfbb3in___5->evalfreturnin, Arg_0: Arg_1 {O(n)} 400: n_evalfbb3in___5->evalfreturnin, Arg_1: 255 {O(1)} 369: n_evalfbb3in___6->n_evalfbbin___3, Arg_0: -1 {O(1)} 369: n_evalfbb3in___6->n_evalfbbin___3, Arg_1: 254 {O(1)} 392: n_evalfbb3in___6->evalfreturnin, Arg_0: -(inf) {Infinity} 392: n_evalfbb3in___6->evalfreturnin, Arg_1: -(inf) {Infinity} 395: n_evalfbb3in___6->evalfreturnin, Arg_0: -1 {O(1)} 395: n_evalfbb3in___6->evalfreturnin, Arg_1: 255 {O(1)} 398: n_evalfbb3in___6->evalfreturnin, Arg_0: -(inf) {Infinity} 398: n_evalfbb3in___6->evalfreturnin, Arg_1: -(inf) {Infinity} 401: n_evalfbb3in___6->evalfreturnin, Arg_0: -1 {O(1)} 401: n_evalfbb3in___6->evalfreturnin, Arg_1: 255 {O(1)} 371: n_evalfbbin___1->n_evalfbb3in___4, Arg_0: 0 {O(1)} 371: n_evalfbbin___1->n_evalfbb3in___4, Arg_1: 253 {O(1)} 372: n_evalfbbin___2->n_evalfbb3in___5, Arg_0: Arg_1 {O(n)} 372: n_evalfbbin___2->n_evalfbb3in___5, Arg_1: 255 {O(1)} 373: n_evalfbbin___3->n_evalfbb3in___6, Arg_0: -1 {O(1)} 373: n_evalfbbin___3->n_evalfbb3in___6, Arg_1: 255 {O(1)} 374: n_evalfbbin___7->n_evalfbb3in___4, Arg_0: 0 {O(1)} 374: n_evalfbbin___7->n_evalfbb3in___4, Arg_1: 253 {O(1)} 375: n_evalfbbin___7->n_evalfbb3in___5, Arg_0: Arg_1 {O(n)} 375: n_evalfbbin___7->n_evalfbb3in___5, Arg_1: 255 {O(1)} 376: n_evalfbbin___7->n_evalfbb3in___6, Arg_0: -1 {O(1)} 376: n_evalfbbin___7->n_evalfbb3in___6, Arg_1: 255 {O(1)} ---------------------------------------- (2) BOUNDS(1, max(256 + -254 * Arg_1, 510) + max(-1 + 254 * Arg_1, 253) + max(-507 + -64516 * Arg_1, 64009) + max(62756 + 193803 * Arg_1, 256559))