/export/starexec/sandbox/solver/bin/starexec_run_complexity /export/starexec/sandbox/benchmark/theBenchmark.koat /export/starexec/sandbox/output/output_files -------------------------------------------------------------------------------- WORST_CASE(Omega(n^1), 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(n^1, max(6, 24354 + -221 * Arg_0) + nat(101 + -1 * Arg_0) + nat(111 + -1 * Arg_0) + nat(60702 + -551 * Arg_0) + max(2, 113 + -1 * Arg_0) + nat(max(2, 113 + -1 * Arg_0) * max(24348 + -221 * Arg_0, -183) + nat(24348 + -221 * Arg_0) * max(24348 + -221 * Arg_0, -183)) + max(4, 448 + -4 * Arg_0) + nat(max(1, 112 + -1 * Arg_0) * max(24348 + -221 * Arg_0, -183) + nat(24348 + -221 * Arg_0) * max(24348 + -221 * Arg_0, -183))). (0) CpxIntTrs (1) Koat2 Proof [FINISHED, 2969 ms] (2) BOUNDS(1, max(6, 24354 + -221 * Arg_0) + nat(101 + -1 * Arg_0) + nat(111 + -1 * Arg_0) + nat(60702 + -551 * Arg_0) + max(2, 113 + -1 * Arg_0) + nat(max(2, 113 + -1 * Arg_0) * max(24348 + -221 * Arg_0, -183) + nat(24348 + -221 * Arg_0) * max(24348 + -221 * Arg_0, -183)) + max(4, 448 + -4 * Arg_0) + nat(max(1, 112 + -1 * Arg_0) * max(24348 + -221 * Arg_0, -183) + nat(24348 + -221 * Arg_0) * max(24348 + -221 * Arg_0, -183))) (3) Loat Proof [FINISHED, 522 ms] (4) BOUNDS(n^1, INF) ---------------------------------------- (0) Obligation: Complexity Int TRS consisting of the following rules: evalsipma91start(A, B, C, D) -> Com_1(evalsipma91entryin(A, B, C, D)) :|: TRUE evalsipma91entryin(A, B, C, D) -> Com_1(evalsipma91returnin(A, B, C, D)) :|: A >= 101 evalsipma91entryin(A, B, C, D) -> Com_1(evalsipma91bb3in(1, A, C, D)) :|: 100 >= A evalsipma91bb3in(A, B, C, D) -> Com_1(evalsipma91bb2in(A, B, C, D)) :|: 100 >= B evalsipma91bb3in(A, B, C, D) -> Com_1(evalsipma91bb11in(A, B, C, D)) :|: B >= 101 evalsipma91bb2in(A, B, C, D) -> Com_1(evalsipma91bb3in(A + 1, B + 11, C, D)) :|: TRUE evalsipma91bb11in(A, B, C, D) -> Com_1(evalsipma91bb5in(A, B, C, D)) :|: A >= 2 evalsipma91bb11in(A, B, C, D) -> Com_1(evalsipma91returnin(A, B, C, D)) :|: 1 >= A evalsipma91bb5in(A, B, C, D) -> Com_1(evalsipma91bb8in(A, B, B - 10, A - 1)) :|: 110 >= B evalsipma91bb5in(A, B, C, D) -> Com_1(evalsipma91bb8in(A, B, B - 10, A - 1)) :|: 1 >= A evalsipma91bb5in(A, B, C, D) -> Com_1(evalsipma91bb8in(A, B, B - 10, A - 1)) :|: A >= 3 evalsipma91bb5in(A, B, C, D) -> Com_1(evalsipma91bb11in(A - 1, B - 10, C, D)) :|: B >= 111 && A >= 2 && A <= 2 evalsipma91bb8in(A, B, C, D) -> Com_1(evalsipma91bb11in(D, C + 1, C, D)) :|: C >= 101 evalsipma91bb8in(A, B, C, D) -> Com_1(evalsipma91bb11in(D, C + 11, C, D)) :|: C >= 101 && 100 >= C evalsipma91bb8in(A, B, C, D) -> Com_1(evalsipma91bb11in(D + 1, C + 1, C, D)) :|: 100 >= C && C >= 101 evalsipma91bb8in(A, B, C, D) -> Com_1(evalsipma91bb11in(D + 1, C + 11, C, D)) :|: 100 >= C evalsipma91returnin(A, B, C, D) -> Com_1(evalsipma91stop(A, B, C, D)) :|: TRUE The start-symbols are:[evalsipma91start_4] ---------------------------------------- (1) Koat2 Proof (FINISHED) YES( ?, 6+max([0, max([-183, -404+221*max([1, 112-Arg_0])])])+max([0, 101-Arg_0])+max([2, 2*max([1, 112-Arg_0])])+max([1, 112-Arg_0])+max([0, (max([1, 112-Arg_0])+max([0, max([-183, -404+221*max([1, 112-Arg_0])])]))*max([-183, -404+221*max([1, 112-Arg_0])])])+max([0, 111-Arg_0])+max([0, max([-459, -1010+551*max([1, 112-Arg_0])])])+max([0, (1+max([1, 112-Arg_0])+max([0, max([-183, -404+221*max([1, 112-Arg_0])])]))*max([-183, -404+221*max([1, 112-Arg_0])])])+max([1, 112-Arg_0])+max([2, 113-Arg_0]) {O(n^2)}) Initial Complexity Problem: Start: evalsipma91start Program_Vars: Arg_0, Arg_1, Arg_2, Arg_3 Temp_Vars: Locations: evalsipma91bb11in, evalsipma91bb2in, evalsipma91bb3in, evalsipma91bb5in, evalsipma91bb8in, evalsipma91entryin, evalsipma91returnin, evalsipma91start, evalsipma91stop Transitions: evalsipma91bb11in(Arg_0,Arg_1,Arg_2,Arg_3) -> evalsipma91bb5in(Arg_0,Arg_1,Arg_2,Arg_3):|:101 <= Arg_1 && 102 <= Arg_0+Arg_1 && 1 <= Arg_0 && 2 <= Arg_0 evalsipma91bb11in(Arg_0,Arg_1,Arg_2,Arg_3) -> evalsipma91returnin(Arg_0,Arg_1,Arg_2,Arg_3):|:101 <= Arg_1 && 102 <= Arg_0+Arg_1 && 1 <= Arg_0 && Arg_0 <= 1 evalsipma91bb2in(Arg_0,Arg_1,Arg_2,Arg_3) -> evalsipma91bb3in(Arg_0+1,Arg_1+11,Arg_2,Arg_3):|:Arg_1 <= 100 && Arg_1 <= 99+Arg_0 && 1 <= Arg_0 evalsipma91bb3in(Arg_0,Arg_1,Arg_2,Arg_3) -> evalsipma91bb11in(Arg_0,Arg_1,Arg_2,Arg_3):|:1 <= Arg_0 && 101 <= Arg_1 evalsipma91bb3in(Arg_0,Arg_1,Arg_2,Arg_3) -> evalsipma91bb2in(Arg_0,Arg_1,Arg_2,Arg_3):|:1 <= Arg_0 && Arg_1 <= 100 evalsipma91bb5in(Arg_0,Arg_1,Arg_2,Arg_3) -> evalsipma91bb11in(Arg_0-1,Arg_1-10,Arg_2,Arg_3):|:101 <= Arg_1 && 103 <= Arg_0+Arg_1 && 2 <= Arg_0 && 111 <= Arg_1 && Arg_0 <= 2 && 2 <= Arg_0 evalsipma91bb5in(Arg_0,Arg_1,Arg_2,Arg_3) -> evalsipma91bb8in(Arg_0,Arg_1,Arg_1-10,Arg_0-1):|:101 <= Arg_1 && 103 <= Arg_0+Arg_1 && 2 <= Arg_0 && Arg_1 <= 110 evalsipma91bb5in(Arg_0,Arg_1,Arg_2,Arg_3) -> evalsipma91bb8in(Arg_0,Arg_1,Arg_1-10,Arg_0-1):|:101 <= Arg_1 && 103 <= Arg_0+Arg_1 && 2 <= Arg_0 && 3 <= Arg_0 evalsipma91bb8in(Arg_0,Arg_1,Arg_2,Arg_3) -> evalsipma91bb11in(Arg_3,Arg_2+1,Arg_2,Arg_3):|:1+Arg_3 <= Arg_0 && 1 <= Arg_3 && 92 <= Arg_2+Arg_3 && 102 <= Arg_1+Arg_3 && 3 <= Arg_0+Arg_3 && Arg_0 <= 1+Arg_3 && 10+Arg_2 <= Arg_1 && 91 <= Arg_2 && 192 <= Arg_1+Arg_2 && Arg_1 <= 10+Arg_2 && 93 <= Arg_0+Arg_2 && 101 <= Arg_1 && 103 <= Arg_0+Arg_1 && 2 <= Arg_0 && 101 <= Arg_2 evalsipma91bb8in(Arg_0,Arg_1,Arg_2,Arg_3) -> evalsipma91bb11in(Arg_3+1,Arg_2+11,Arg_2,Arg_3):|:1+Arg_3 <= Arg_0 && 1 <= Arg_3 && 92 <= Arg_2+Arg_3 && 102 <= Arg_1+Arg_3 && 3 <= Arg_0+Arg_3 && Arg_0 <= 1+Arg_3 && 10+Arg_2 <= Arg_1 && 91 <= Arg_2 && 192 <= Arg_1+Arg_2 && Arg_1 <= 10+Arg_2 && 93 <= Arg_0+Arg_2 && 101 <= Arg_1 && 103 <= Arg_0+Arg_1 && 2 <= Arg_0 && Arg_2 <= 100 evalsipma91entryin(Arg_0,Arg_1,Arg_2,Arg_3) -> evalsipma91bb3in(1,Arg_0,Arg_2,Arg_3):|:Arg_0 <= 100 evalsipma91entryin(Arg_0,Arg_1,Arg_2,Arg_3) -> evalsipma91returnin(Arg_0,Arg_1,Arg_2,Arg_3):|:101 <= Arg_0 evalsipma91returnin(Arg_0,Arg_1,Arg_2,Arg_3) -> evalsipma91stop(Arg_0,Arg_1,Arg_2,Arg_3):|: evalsipma91start(Arg_0,Arg_1,Arg_2,Arg_3) -> evalsipma91entryin(Arg_0,Arg_1,Arg_2,Arg_3):|: Timebounds: Overall timebound: 6+max([0, max([-183, -404+221*max([1, 112-Arg_0])])])+max([0, 101-Arg_0])+max([2, 2*max([1, 112-Arg_0])])+max([1, 112-Arg_0])+max([0, (max([1, 112-Arg_0])+max([0, max([-183, -404+221*max([1, 112-Arg_0])])]))*max([-183, -404+221*max([1, 112-Arg_0])])])+max([0, 111-Arg_0])+max([0, max([-459, -1010+551*max([1, 112-Arg_0])])])+max([0, (1+max([1, 112-Arg_0])+max([0, max([-183, -404+221*max([1, 112-Arg_0])])]))*max([-183, -404+221*max([1, 112-Arg_0])])])+max([1, 112-Arg_0])+max([2, 113-Arg_0]) {O(n^2)} 6: evalsipma91bb11in->evalsipma91bb5in: max([0, (1+max([1, 112-Arg_0])+max([0, max([-183, -404+221*max([1, 112-Arg_0])])]))*max([-183, -404+221*max([1, 112-Arg_0])])])+max([2, 113-Arg_0]) {O(n^2)} 7: evalsipma91bb11in->evalsipma91returnin: 1 {O(1)} 5: evalsipma91bb2in->evalsipma91bb3in: max([0, 111-Arg_0]) {O(n)} 3: evalsipma91bb3in->evalsipma91bb2in: max([0, 101-Arg_0]) {O(n)} 4: evalsipma91bb3in->evalsipma91bb11in: 1 {O(1)} 8: evalsipma91bb5in->evalsipma91bb8in: max([0, max([-459, -1010+551*max([1, 112-Arg_0])])]) {O(n)} 10: evalsipma91bb5in->evalsipma91bb8in: max([0, (max([1, 112-Arg_0])+max([0, max([-183, -404+221*max([1, 112-Arg_0])])]))*max([-183, -404+221*max([1, 112-Arg_0])])])+max([1, 112-Arg_0]) {O(n^2)} 11: evalsipma91bb5in->evalsipma91bb11in: max([1, 112-Arg_0]) {O(n)} 12: evalsipma91bb8in->evalsipma91bb11in: max([2, 2*max([1, 112-Arg_0])]) {O(n)} 15: evalsipma91bb8in->evalsipma91bb11in: max([0, max([-183, -404+221*max([1, 112-Arg_0])])]) {O(n)} 1: evalsipma91entryin->evalsipma91returnin: 1 {O(1)} 2: evalsipma91entryin->evalsipma91bb3in: 1 {O(1)} 16: evalsipma91returnin->evalsipma91stop: 1 {O(1)} 0: evalsipma91start->evalsipma91entryin: 1 {O(1)} Costbounds: Overall costbound: 6+max([0, max([-183, -404+221*max([1, 112-Arg_0])])])+max([0, 101-Arg_0])+max([2, 2*max([1, 112-Arg_0])])+max([1, 112-Arg_0])+max([0, (max([1, 112-Arg_0])+max([0, max([-183, -404+221*max([1, 112-Arg_0])])]))*max([-183, -404+221*max([1, 112-Arg_0])])])+max([0, 111-Arg_0])+max([0, max([-459, -1010+551*max([1, 112-Arg_0])])])+max([0, (1+max([1, 112-Arg_0])+max([0, max([-183, -404+221*max([1, 112-Arg_0])])]))*max([-183, -404+221*max([1, 112-Arg_0])])])+max([1, 112-Arg_0])+max([2, 113-Arg_0]) {O(n^2)} 6: evalsipma91bb11in->evalsipma91bb5in: max([0, (1+max([1, 112-Arg_0])+max([0, max([-183, -404+221*max([1, 112-Arg_0])])]))*max([-183, -404+221*max([1, 112-Arg_0])])])+max([2, 113-Arg_0]) {O(n^2)} 7: evalsipma91bb11in->evalsipma91returnin: 1 {O(1)} 5: evalsipma91bb2in->evalsipma91bb3in: max([0, 111-Arg_0]) {O(n)} 3: evalsipma91bb3in->evalsipma91bb2in: max([0, 101-Arg_0]) {O(n)} 4: evalsipma91bb3in->evalsipma91bb11in: 1 {O(1)} 8: evalsipma91bb5in->evalsipma91bb8in: max([0, max([-459, -1010+551*max([1, 112-Arg_0])])]) {O(n)} 10: evalsipma91bb5in->evalsipma91bb8in: max([0, (max([1, 112-Arg_0])+max([0, max([-183, -404+221*max([1, 112-Arg_0])])]))*max([-183, -404+221*max([1, 112-Arg_0])])])+max([1, 112-Arg_0]) {O(n^2)} 11: evalsipma91bb5in->evalsipma91bb11in: max([1, 112-Arg_0]) {O(n)} 12: evalsipma91bb8in->evalsipma91bb11in: max([2, 2*max([1, 112-Arg_0])]) {O(n)} 15: evalsipma91bb8in->evalsipma91bb11in: max([0, max([-183, -404+221*max([1, 112-Arg_0])])]) {O(n)} 1: evalsipma91entryin->evalsipma91returnin: 1 {O(1)} 2: evalsipma91entryin->evalsipma91bb3in: 1 {O(1)} 16: evalsipma91returnin->evalsipma91stop: 1 {O(1)} 0: evalsipma91start->evalsipma91entryin: 1 {O(1)} Sizebounds: `Lower: 6: evalsipma91bb11in->evalsipma91bb5in, Arg_0: 2 {O(1)} 6: evalsipma91bb11in->evalsipma91bb5in, Arg_1: 101 {O(1)} 6: evalsipma91bb11in->evalsipma91bb5in, Arg_2: min([91, Arg_2]) {O(n)} 6: evalsipma91bb11in->evalsipma91bb5in, Arg_3: min([1, Arg_3]) {O(n)} 7: evalsipma91bb11in->evalsipma91returnin, Arg_0: 1 {O(1)} 7: evalsipma91bb11in->evalsipma91returnin, Arg_1: 101 {O(1)} 7: evalsipma91bb11in->evalsipma91returnin, Arg_2: min([91, min([101, Arg_2])]) {O(n)} 7: evalsipma91bb11in->evalsipma91returnin, Arg_3: min([1, Arg_3]) {O(n)} 5: evalsipma91bb2in->evalsipma91bb3in, Arg_0: 2 {O(1)} 5: evalsipma91bb2in->evalsipma91bb3in, Arg_1: Arg_0 {O(n)} 5: evalsipma91bb2in->evalsipma91bb3in, Arg_2: Arg_2 {O(n)} 5: evalsipma91bb2in->evalsipma91bb3in, Arg_3: Arg_3 {O(n)} 3: evalsipma91bb3in->evalsipma91bb2in, Arg_0: 1 {O(1)} 3: evalsipma91bb3in->evalsipma91bb2in, Arg_1: Arg_0 {O(n)} 3: evalsipma91bb3in->evalsipma91bb2in, Arg_2: Arg_2 {O(n)} 3: evalsipma91bb3in->evalsipma91bb2in, Arg_3: Arg_3 {O(n)} 4: evalsipma91bb3in->evalsipma91bb11in, Arg_0: 1 {O(1)} 4: evalsipma91bb3in->evalsipma91bb11in, Arg_1: 101 {O(1)} 4: evalsipma91bb3in->evalsipma91bb11in, Arg_2: Arg_2 {O(n)} 4: evalsipma91bb3in->evalsipma91bb11in, Arg_3: Arg_3 {O(n)} 8: evalsipma91bb5in->evalsipma91bb8in, Arg_0: 2 {O(1)} 8: evalsipma91bb5in->evalsipma91bb8in, Arg_1: 101 {O(1)} 8: evalsipma91bb5in->evalsipma91bb8in, Arg_2: 91 {O(1)} 8: evalsipma91bb5in->evalsipma91bb8in, Arg_3: 1 {O(1)} 10: evalsipma91bb5in->evalsipma91bb8in, Arg_0: 3 {O(1)} 10: evalsipma91bb5in->evalsipma91bb8in, Arg_1: 101 {O(1)} 10: evalsipma91bb5in->evalsipma91bb8in, Arg_2: 91 {O(1)} 10: evalsipma91bb5in->evalsipma91bb8in, Arg_3: 2 {O(1)} 11: evalsipma91bb5in->evalsipma91bb11in, Arg_0: 1 {O(1)} 11: evalsipma91bb5in->evalsipma91bb11in, Arg_1: 101 {O(1)} 11: evalsipma91bb5in->evalsipma91bb11in, Arg_2: min([91, Arg_2]) {O(n)} 11: evalsipma91bb5in->evalsipma91bb11in, Arg_3: min([1, Arg_3]) {O(n)} 12: evalsipma91bb8in->evalsipma91bb11in, Arg_0: 1 {O(1)} 12: evalsipma91bb8in->evalsipma91bb11in, Arg_1: 102 {O(1)} 12: evalsipma91bb8in->evalsipma91bb11in, Arg_2: 101 {O(1)} 12: evalsipma91bb8in->evalsipma91bb11in, Arg_3: 1 {O(1)} 15: evalsipma91bb8in->evalsipma91bb11in, Arg_0: 2 {O(1)} 15: evalsipma91bb8in->evalsipma91bb11in, Arg_1: 102 {O(1)} 15: evalsipma91bb8in->evalsipma91bb11in, Arg_2: 91 {O(1)} 15: evalsipma91bb8in->evalsipma91bb11in, Arg_3: 1 {O(1)} 1: evalsipma91entryin->evalsipma91returnin, Arg_0: 101 {O(1)} 1: evalsipma91entryin->evalsipma91returnin, Arg_1: Arg_1 {O(n)} 1: evalsipma91entryin->evalsipma91returnin, Arg_2: Arg_2 {O(n)} 1: evalsipma91entryin->evalsipma91returnin, Arg_3: Arg_3 {O(n)} 2: evalsipma91entryin->evalsipma91bb3in, Arg_0: 1 {O(1)} 2: evalsipma91entryin->evalsipma91bb3in, Arg_1: Arg_0 {O(n)} 2: evalsipma91entryin->evalsipma91bb3in, Arg_2: Arg_2 {O(n)} 2: evalsipma91entryin->evalsipma91bb3in, Arg_3: Arg_3 {O(n)} 16: evalsipma91returnin->evalsipma91stop, Arg_0: 1 {O(1)} 16: evalsipma91returnin->evalsipma91stop, Arg_1: min([101, Arg_1]) {O(n)} 16: evalsipma91returnin->evalsipma91stop, Arg_2: min([91, min([101, Arg_2])]) {O(n)} 16: evalsipma91returnin->evalsipma91stop, Arg_3: min([1, Arg_3]) {O(n)} 0: evalsipma91start->evalsipma91entryin, Arg_0: Arg_0 {O(n)} 0: evalsipma91start->evalsipma91entryin, Arg_1: Arg_1 {O(n)} 0: evalsipma91start->evalsipma91entryin, Arg_2: Arg_2 {O(n)} 0: evalsipma91start->evalsipma91entryin, Arg_3: Arg_3 {O(n)} `Upper: 6: evalsipma91bb11in->evalsipma91bb5in, Arg_0: max([1, 112-Arg_0])+max([0, max([-183, -404+221*max([1, 112-Arg_0])])]) {O(n)} 6: evalsipma91bb11in->evalsipma91bb5in, Arg_1: max([113, 111+2*max([1, 112-Arg_0])]) {O(n)} 6: evalsipma91bb11in->evalsipma91bb5in, Arg_2: max([113, max([100, max([Arg_2, 111+2*max([1, 112-Arg_0])])])]) {O(n)} 6: evalsipma91bb11in->evalsipma91bb5in, Arg_3: max([Arg_3, max([1, 112-Arg_0])+max([0, max([-183, -404+221*max([1, 112-Arg_0])])])]) {O(n)} 7: evalsipma91bb11in->evalsipma91returnin, Arg_0: 1 {O(1)} 7: evalsipma91bb11in->evalsipma91returnin, Arg_1: max([111, max([113, max([101+2*max([1, 112-Arg_0]), 111+2*max([1, 112-Arg_0])])])]) {O(n)} 7: evalsipma91bb11in->evalsipma91returnin, Arg_2: max([100, max([113, max([113, max([Arg_2, max([Arg_2, 111+2*max([1, 112-Arg_0])])])])])]) {O(n)} 7: evalsipma91bb11in->evalsipma91returnin, Arg_3: max([Arg_3, max([1, 112-Arg_0])+max([0, max([-183, -404+221*max([1, 112-Arg_0])])])]) {O(n)} 5: evalsipma91bb2in->evalsipma91bb3in, Arg_0: max([1, 112-Arg_0]) {O(n)} 5: evalsipma91bb2in->evalsipma91bb3in, Arg_1: 111 {O(1)} 5: evalsipma91bb2in->evalsipma91bb3in, Arg_2: Arg_2 {O(n)} 5: evalsipma91bb2in->evalsipma91bb3in, Arg_3: Arg_3 {O(n)} 3: evalsipma91bb3in->evalsipma91bb2in, Arg_0: max([1, 112-Arg_0]) {O(n)} 3: evalsipma91bb3in->evalsipma91bb2in, Arg_1: 100 {O(1)} 3: evalsipma91bb3in->evalsipma91bb2in, Arg_2: Arg_2 {O(n)} 3: evalsipma91bb3in->evalsipma91bb2in, Arg_3: Arg_3 {O(n)} 4: evalsipma91bb3in->evalsipma91bb11in, Arg_0: max([1, 112-Arg_0]) {O(n)} 4: evalsipma91bb3in->evalsipma91bb11in, Arg_1: 111 {O(1)} 4: evalsipma91bb3in->evalsipma91bb11in, Arg_2: Arg_2 {O(n)} 4: evalsipma91bb3in->evalsipma91bb11in, Arg_3: Arg_3 {O(n)} 8: evalsipma91bb5in->evalsipma91bb8in, Arg_0: max([1, 112-Arg_0])+max([0, max([-183, -404+221*max([1, 112-Arg_0])])]) {O(n)} 8: evalsipma91bb5in->evalsipma91bb8in, Arg_1: 110 {O(1)} 8: evalsipma91bb5in->evalsipma91bb8in, Arg_2: 100 {O(1)} 8: evalsipma91bb5in->evalsipma91bb8in, Arg_3: max([1, 112-Arg_0])+max([0, max([-183, -404+221*max([1, 112-Arg_0])])]) {O(n)} 10: evalsipma91bb5in->evalsipma91bb8in, Arg_0: max([1, 112-Arg_0])+max([0, max([-183, -404+221*max([1, 112-Arg_0])])]) {O(n)} 10: evalsipma91bb5in->evalsipma91bb8in, Arg_1: max([113, 111+2*max([1, 112-Arg_0])]) {O(n)} 10: evalsipma91bb5in->evalsipma91bb8in, Arg_2: max([113, 111+2*max([1, 112-Arg_0])]) {O(n)} 10: evalsipma91bb5in->evalsipma91bb8in, Arg_3: max([1, 112-Arg_0])+max([0, max([-183, -404+221*max([1, 112-Arg_0])])]) {O(n)} 11: evalsipma91bb5in->evalsipma91bb11in, Arg_0: 1 {O(1)} 11: evalsipma91bb5in->evalsipma91bb11in, Arg_1: max([103, 101+2*max([1, 112-Arg_0])]) {O(n)} 11: evalsipma91bb5in->evalsipma91bb11in, Arg_2: max([113, max([100, max([Arg_2, 111+2*max([1, 112-Arg_0])])])]) {O(n)} 11: evalsipma91bb5in->evalsipma91bb11in, Arg_3: max([Arg_3, max([1, 112-Arg_0])+max([0, max([-183, -404+221*max([1, 112-Arg_0])])])]) {O(n)} 12: evalsipma91bb8in->evalsipma91bb11in, Arg_0: max([1, 112-Arg_0])+max([0, max([-183, -404+221*max([1, 112-Arg_0])])]) {O(n)} 12: evalsipma91bb8in->evalsipma91bb11in, Arg_1: max([113, 111+2*max([1, 112-Arg_0])]) {O(n)} 12: evalsipma91bb8in->evalsipma91bb11in, Arg_2: max([113, 111+2*max([1, 112-Arg_0])]) {O(n)} 12: evalsipma91bb8in->evalsipma91bb11in, Arg_3: max([1, 112-Arg_0])+max([0, max([-183, -404+221*max([1, 112-Arg_0])])]) {O(n)} 15: evalsipma91bb8in->evalsipma91bb11in, Arg_0: max([1, 112-Arg_0])+max([0, max([-183, -404+221*max([1, 112-Arg_0])])]) {O(n)} 15: evalsipma91bb8in->evalsipma91bb11in, Arg_1: 111 {O(1)} 15: evalsipma91bb8in->evalsipma91bb11in, Arg_2: 100 {O(1)} 15: evalsipma91bb8in->evalsipma91bb11in, Arg_3: max([1, 112-Arg_0])+max([0, max([-183, -404+221*max([1, 112-Arg_0])])]) {O(n)} 1: evalsipma91entryin->evalsipma91returnin, Arg_0: Arg_0 {O(n)} 1: evalsipma91entryin->evalsipma91returnin, Arg_1: Arg_1 {O(n)} 1: evalsipma91entryin->evalsipma91returnin, Arg_2: Arg_2 {O(n)} 1: evalsipma91entryin->evalsipma91returnin, Arg_3: Arg_3 {O(n)} 2: evalsipma91entryin->evalsipma91bb3in, Arg_0: 1 {O(1)} 2: evalsipma91entryin->evalsipma91bb3in, Arg_1: 100 {O(1)} 2: evalsipma91entryin->evalsipma91bb3in, Arg_2: Arg_2 {O(n)} 2: evalsipma91entryin->evalsipma91bb3in, Arg_3: Arg_3 {O(n)} 16: evalsipma91returnin->evalsipma91stop, Arg_0: max([1, Arg_0]) {O(n)} 16: evalsipma91returnin->evalsipma91stop, Arg_1: max([111, max([113, max([Arg_1, max([101+2*max([1, 112-Arg_0]), 111+2*max([1, 112-Arg_0])])])])]) {O(n)} 16: evalsipma91returnin->evalsipma91stop, Arg_2: max([100, max([113, max([113, max([Arg_2, max([Arg_2, max([Arg_2, 111+2*max([1, 112-Arg_0])])])])])])]) {O(n)} 16: evalsipma91returnin->evalsipma91stop, Arg_3: max([Arg_3, max([Arg_3, max([1, 112-Arg_0])+max([0, max([-183, -404+221*max([1, 112-Arg_0])])])])]) {O(n)} 0: evalsipma91start->evalsipma91entryin, Arg_0: Arg_0 {O(n)} 0: evalsipma91start->evalsipma91entryin, Arg_1: Arg_1 {O(n)} 0: evalsipma91start->evalsipma91entryin, Arg_2: Arg_2 {O(n)} 0: evalsipma91start->evalsipma91entryin, Arg_3: Arg_3 {O(n)} ---------------------------------------- (2) BOUNDS(1, max(6, 24354 + -221 * Arg_0) + nat(101 + -1 * Arg_0) + nat(111 + -1 * Arg_0) + nat(60702 + -551 * Arg_0) + max(2, 113 + -1 * Arg_0) + nat(max(2, 113 + -1 * Arg_0) * max(24348 + -221 * Arg_0, -183) + nat(24348 + -221 * Arg_0) * max(24348 + -221 * Arg_0, -183)) + max(4, 448 + -4 * Arg_0) + nat(max(1, 112 + -1 * Arg_0) * max(24348 + -221 * Arg_0, -183) + nat(24348 + -221 * Arg_0) * max(24348 + -221 * Arg_0, -183))) ---------------------------------------- (3) Loat Proof (FINISHED) ### Pre-processing the ITS problem ### Initial linear ITS problem Start location: evalsipma91start 0: evalsipma91start -> evalsipma91entryin : [], cost: 1 1: evalsipma91entryin -> evalsipma91returnin : [ A>=101 ], cost: 1 2: evalsipma91entryin -> evalsipma91bb3in : A'=1, B'=A, [ 100>=A ], cost: 1 3: evalsipma91bb3in -> evalsipma91bb2in : [ 100>=B ], cost: 1 4: evalsipma91bb3in -> evalsipma91bb11in : [ B>=101 ], cost: 1 5: evalsipma91bb2in -> evalsipma91bb3in : A'=1+A, B'=11+B, [], cost: 1 6: evalsipma91bb11in -> evalsipma91bb5in : [ A>=2 ], cost: 1 7: evalsipma91bb11in -> evalsipma91returnin : [ 1>=A ], cost: 1 8: evalsipma91bb5in -> evalsipma91bb8in : C'=-10+B, D'=-1+A, [ 110>=B ], cost: 1 9: evalsipma91bb5in -> evalsipma91bb8in : C'=-10+B, D'=-1+A, [ 1>=A ], cost: 1 10: evalsipma91bb5in -> evalsipma91bb8in : C'=-10+B, D'=-1+A, [ A>=3 ], cost: 1 11: evalsipma91bb5in -> evalsipma91bb11in : A'=-1+A, B'=-10+B, [ B>=111 && A==2 ], cost: 1 12: evalsipma91bb8in -> evalsipma91bb11in : A'=D, B'=1+C, [ C>=101 ], cost: 1 13: evalsipma91bb8in -> evalsipma91bb11in : A'=D, B'=11+C, [ C>=101 && 100>=C ], cost: 1 14: evalsipma91bb8in -> evalsipma91bb11in : A'=1+D, B'=1+C, [ 100>=C && C>=101 ], cost: 1 15: evalsipma91bb8in -> evalsipma91bb11in : A'=1+D, B'=11+C, [ 100>=C ], cost: 1 16: evalsipma91returnin -> evalsipma91stop : [], cost: 1 Removed unreachable and leaf rules: Start location: evalsipma91start 0: evalsipma91start -> evalsipma91entryin : [], cost: 1 2: evalsipma91entryin -> evalsipma91bb3in : A'=1, B'=A, [ 100>=A ], cost: 1 3: evalsipma91bb3in -> evalsipma91bb2in : [ 100>=B ], cost: 1 4: evalsipma91bb3in -> evalsipma91bb11in : [ B>=101 ], cost: 1 5: evalsipma91bb2in -> evalsipma91bb3in : A'=1+A, B'=11+B, [], cost: 1 6: evalsipma91bb11in -> evalsipma91bb5in : [ A>=2 ], cost: 1 8: evalsipma91bb5in -> evalsipma91bb8in : C'=-10+B, D'=-1+A, [ 110>=B ], cost: 1 9: evalsipma91bb5in -> evalsipma91bb8in : C'=-10+B, D'=-1+A, [ 1>=A ], cost: 1 10: evalsipma91bb5in -> evalsipma91bb8in : C'=-10+B, D'=-1+A, [ A>=3 ], cost: 1 11: evalsipma91bb5in -> evalsipma91bb11in : A'=-1+A, B'=-10+B, [ B>=111 && A==2 ], cost: 1 12: evalsipma91bb8in -> evalsipma91bb11in : A'=D, B'=1+C, [ C>=101 ], cost: 1 13: evalsipma91bb8in -> evalsipma91bb11in : A'=D, B'=11+C, [ C>=101 && 100>=C ], cost: 1 14: evalsipma91bb8in -> evalsipma91bb11in : A'=1+D, B'=1+C, [ 100>=C && C>=101 ], cost: 1 15: evalsipma91bb8in -> evalsipma91bb11in : A'=1+D, B'=11+C, [ 100>=C ], cost: 1 Removed rules with unsatisfiable guard: Start location: evalsipma91start 0: evalsipma91start -> evalsipma91entryin : [], cost: 1 2: evalsipma91entryin -> evalsipma91bb3in : A'=1, B'=A, [ 100>=A ], cost: 1 3: evalsipma91bb3in -> evalsipma91bb2in : [ 100>=B ], cost: 1 4: evalsipma91bb3in -> evalsipma91bb11in : [ B>=101 ], cost: 1 5: evalsipma91bb2in -> evalsipma91bb3in : A'=1+A, B'=11+B, [], cost: 1 6: evalsipma91bb11in -> evalsipma91bb5in : [ A>=2 ], cost: 1 8: evalsipma91bb5in -> evalsipma91bb8in : C'=-10+B, D'=-1+A, [ 110>=B ], cost: 1 9: evalsipma91bb5in -> evalsipma91bb8in : C'=-10+B, D'=-1+A, [ 1>=A ], cost: 1 10: evalsipma91bb5in -> evalsipma91bb8in : C'=-10+B, D'=-1+A, [ A>=3 ], cost: 1 11: evalsipma91bb5in -> evalsipma91bb11in : A'=-1+A, B'=-10+B, [ B>=111 && A==2 ], cost: 1 12: evalsipma91bb8in -> evalsipma91bb11in : A'=D, B'=1+C, [ C>=101 ], cost: 1 15: evalsipma91bb8in -> evalsipma91bb11in : A'=1+D, B'=11+C, [ 100>=C ], cost: 1 ### Simplification by acceleration and chaining ### Eliminated locations (on linear paths): Start location: evalsipma91start 17: evalsipma91start -> evalsipma91bb3in : A'=1, B'=A, [ 100>=A ], cost: 2 4: evalsipma91bb3in -> evalsipma91bb11in : [ B>=101 ], cost: 1 18: evalsipma91bb3in -> evalsipma91bb3in : A'=1+A, B'=11+B, [ 100>=B ], cost: 2 6: evalsipma91bb11in -> evalsipma91bb5in : [ A>=2 ], cost: 1 8: evalsipma91bb5in -> evalsipma91bb8in : C'=-10+B, D'=-1+A, [ 110>=B ], cost: 1 9: evalsipma91bb5in -> evalsipma91bb8in : C'=-10+B, D'=-1+A, [ 1>=A ], cost: 1 10: evalsipma91bb5in -> evalsipma91bb8in : C'=-10+B, D'=-1+A, [ A>=3 ], cost: 1 11: evalsipma91bb5in -> evalsipma91bb11in : A'=-1+A, B'=-10+B, [ B>=111 && A==2 ], cost: 1 12: evalsipma91bb8in -> evalsipma91bb11in : A'=D, B'=1+C, [ C>=101 ], cost: 1 15: evalsipma91bb8in -> evalsipma91bb11in : A'=1+D, B'=11+C, [ 100>=C ], cost: 1 Accelerating simple loops of location 2. Accelerating the following rules: 18: evalsipma91bb3in -> evalsipma91bb3in : A'=1+A, B'=11+B, [ 100>=B ], cost: 2 Accelerated rule 18 with metering function meter (where 11*meter==100-B), yielding the new rule 19. Removing the simple loops: 18. Accelerated all simple loops using metering functions (where possible): Start location: evalsipma91start 17: evalsipma91start -> evalsipma91bb3in : A'=1, B'=A, [ 100>=A ], cost: 2 4: evalsipma91bb3in -> evalsipma91bb11in : [ B>=101 ], cost: 1 19: evalsipma91bb3in -> evalsipma91bb3in : A'=meter+A, B'=11*meter+B, [ 100>=B && 11*meter==100-B && meter>=1 ], cost: 2*meter 6: evalsipma91bb11in -> evalsipma91bb5in : [ A>=2 ], cost: 1 8: evalsipma91bb5in -> evalsipma91bb8in : C'=-10+B, D'=-1+A, [ 110>=B ], cost: 1 9: evalsipma91bb5in -> evalsipma91bb8in : C'=-10+B, D'=-1+A, [ 1>=A ], cost: 1 10: evalsipma91bb5in -> evalsipma91bb8in : C'=-10+B, D'=-1+A, [ A>=3 ], cost: 1 11: evalsipma91bb5in -> evalsipma91bb11in : A'=-1+A, B'=-10+B, [ B>=111 && A==2 ], cost: 1 12: evalsipma91bb8in -> evalsipma91bb11in : A'=D, B'=1+C, [ C>=101 ], cost: 1 15: evalsipma91bb8in -> evalsipma91bb11in : A'=1+D, B'=11+C, [ 100>=C ], cost: 1 Chained accelerated rules (with incoming rules): Start location: evalsipma91start 17: evalsipma91start -> evalsipma91bb3in : A'=1, B'=A, [ 100>=A ], cost: 2 20: evalsipma91start -> evalsipma91bb3in : A'=1+meter, B'=11*meter+A, [ 100>=A && 11*meter==100-A && meter>=1 ], cost: 2+2*meter 4: evalsipma91bb3in -> evalsipma91bb11in : [ B>=101 ], cost: 1 6: evalsipma91bb11in -> evalsipma91bb5in : [ A>=2 ], cost: 1 8: evalsipma91bb5in -> evalsipma91bb8in : C'=-10+B, D'=-1+A, [ 110>=B ], cost: 1 9: evalsipma91bb5in -> evalsipma91bb8in : C'=-10+B, D'=-1+A, [ 1>=A ], cost: 1 10: evalsipma91bb5in -> evalsipma91bb8in : C'=-10+B, D'=-1+A, [ A>=3 ], cost: 1 11: evalsipma91bb5in -> evalsipma91bb11in : A'=-1+A, B'=-10+B, [ B>=111 && A==2 ], cost: 1 12: evalsipma91bb8in -> evalsipma91bb11in : A'=D, B'=1+C, [ C>=101 ], cost: 1 15: evalsipma91bb8in -> evalsipma91bb11in : A'=1+D, B'=11+C, [ 100>=C ], cost: 1 Eliminated locations (on tree-shaped paths): Start location: evalsipma91start 21: evalsipma91start -> [10] : [ 100>=A && 11*meter==100-A && meter>=1 ], cost: 2+2*meter 6: evalsipma91bb11in -> evalsipma91bb5in : [ A>=2 ], cost: 1 8: evalsipma91bb5in -> evalsipma91bb8in : C'=-10+B, D'=-1+A, [ 110>=B ], cost: 1 9: evalsipma91bb5in -> evalsipma91bb8in : C'=-10+B, D'=-1+A, [ 1>=A ], cost: 1 10: evalsipma91bb5in -> evalsipma91bb8in : C'=-10+B, D'=-1+A, [ A>=3 ], cost: 1 11: evalsipma91bb5in -> evalsipma91bb11in : A'=-1+A, B'=-10+B, [ B>=111 && A==2 ], cost: 1 12: evalsipma91bb8in -> evalsipma91bb11in : A'=D, B'=1+C, [ C>=101 ], cost: 1 15: evalsipma91bb8in -> evalsipma91bb11in : A'=1+D, B'=11+C, [ 100>=C ], cost: 1 Applied pruning (of leafs and parallel rules): Start location: evalsipma91start 21: evalsipma91start -> [10] : [ 100>=A && 11*meter==100-A && meter>=1 ], cost: 2+2*meter ### Computing asymptotic complexity ### Fully simplified ITS problem Start location: evalsipma91start 21: evalsipma91start -> [10] : [ 100>=A && 11*meter==100-A && meter>=1 ], cost: 2+2*meter Computing asymptotic complexity for rule 21 Simplified the guard: 21: evalsipma91start -> [10] : [ 11*meter==100-A && meter>=1 ], cost: 2+2*meter Solved the limit problem by the following transformations: Created initial limit problem: 101-11*meter-A (+/+!), meter (+/+!), -99+11*meter+A (+/+!), 2+2*meter (+) [not solved] applying transformation rule (C) using substitution {A==100-11*meter} resulting limit problem: 1 (+/+!), meter (+/+!), 2+2*meter (+) [not solved] applying transformation rule (B), deleting 1 (+/+!) resulting limit problem: meter (+/+!), 2+2*meter (+) [not solved] removing all constraints (solved by SMT) resulting limit problem: [solved] applying transformation rule (C) using substitution {meter==n} resulting limit problem: [solved] Solution: meter / n A / 100-11*n Resulting cost 2+2*n has complexity: Poly(n^1) Found new complexity Poly(n^1). Obtained the following overall complexity (w.r.t. the length of the input n): Complexity: Poly(n^1) Cpx degree: 1 Solved cost: 2+2*n Rule cost: 2+2*meter Rule guard: [ 11*meter==100-A && meter>=1 ] WORST_CASE(Omega(n^1),?) ---------------------------------------- (4) BOUNDS(n^1, INF)