/export/starexec/sandbox2/solver/bin/starexec_run_complexity /export/starexec/sandbox2/benchmark/theBenchmark.koat /export/starexec/sandbox2/output/output_files -------------------------------------------------------------------------------- WORST_CASE(Omega(n^1), O(n^1)) proof of /export/starexec/sandbox2/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(10 + 5 * Arg_1 + -5 * Arg_2, 5) + nat(1 + 2 * Arg_1 + -2 * Arg_2)). (0) CpxIntTrs (1) Koat2 Proof [FINISHED, 1004 ms] (2) BOUNDS(1, max(10 + 5 * Arg_1 + -5 * Arg_2, 5) + nat(1 + 2 * Arg_1 + -2 * Arg_2)) (3) Loat Proof [FINISHED, 3211 ms] (4) BOUNDS(n^1, INF) ---------------------------------------- (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( ?, 5+2*2*max([0, 1+Arg_1-Arg_2])+max([0, 1+Arg_1-Arg_2])+max([0, 1+-2*Arg_2+2*Arg_1]) {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: evalaaron2bb3in(Arg_0,Arg_1,Arg_2) -> evalaaron2bb4in(Arg_0,Arg_1,Arg_2):|:Arg_1 <= Arg_2 && 0 <= Arg_0 && D+1 <= 0 evalaaron2bb3in(Arg_0,Arg_1,Arg_2) -> evalaaron2bb4in(Arg_0,Arg_1,Arg_2):|:Arg_1 <= Arg_2 && 0 <= Arg_0 && 1 <= D evalaaron2bb3in(Arg_0,Arg_1,Arg_2) -> evalaaron2bb5in(Arg_0,Arg_1,Arg_2):|:Arg_1 <= Arg_2 && 0 <= Arg_0 evalaaron2bb4in(Arg_0,Arg_1,Arg_2) -> evalaaron2bb6in(Arg_0,Arg_1,Arg_2-Arg_0-1):|:Arg_1 <= Arg_2 && 0 <= Arg_0 evalaaron2bb5in(Arg_0,Arg_1,Arg_2) -> evalaaron2bb6in(Arg_0,Arg_1+Arg_0+1,Arg_2):|:Arg_1 <= Arg_2 && 0 <= Arg_0 evalaaron2bb6in(Arg_0,Arg_1,Arg_2) -> evalaaron2bb3in(Arg_0,Arg_1,Arg_2):|:0 <= Arg_0 && Arg_1 <= Arg_2 && 0 <= Arg_0 evalaaron2bb6in(Arg_0,Arg_1,Arg_2) -> evalaaron2returnin(Arg_0,Arg_1,Arg_2):|:0 <= Arg_0 && Arg_2+1 <= Arg_1 evalaaron2entryin(Arg_0,Arg_1,Arg_2) -> evalaaron2bb6in(Arg_0,Arg_2,Arg_1):|:0 <= Arg_0 evalaaron2entryin(Arg_0,Arg_1,Arg_2) -> evalaaron2returnin(Arg_0,Arg_1,Arg_2):|:Arg_0+1 <= 0 evalaaron2returnin(Arg_0,Arg_1,Arg_2) -> evalaaron2stop(Arg_0,Arg_1,Arg_2):|: evalaaron2start(Arg_0,Arg_1,Arg_2) -> evalaaron2entryin(Arg_0,Arg_1,Arg_2):|: Timebounds: Overall timebound: 5+2*2*max([0, 1+Arg_1-Arg_2])+max([0, 1+Arg_1-Arg_2])+max([0, 1+-2*Arg_2+2*Arg_1]) {O(n)} 6: evalaaron2bb3in->evalaaron2bb4in: max([0, 1+Arg_1-Arg_2]) {O(n)} 7: evalaaron2bb3in->evalaaron2bb4in: max([0, 1+Arg_1-Arg_2]) {O(n)} 8: evalaaron2bb3in->evalaaron2bb5in: max([0, 1+Arg_1-Arg_2]) {O(n)} 9: evalaaron2bb4in->evalaaron2bb6in: max([0, 1+-2*Arg_2+2*Arg_1]) {O(n)} 10: evalaaron2bb5in->evalaaron2bb6in: max([0, 1+Arg_1-Arg_2]) {O(n)} 3: evalaaron2bb6in->evalaaron2returnin: 1 {O(1)} 5: evalaaron2bb6in->evalaaron2bb3in: max([0, 1+Arg_1-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: 5+2*2*max([0, 1+Arg_1-Arg_2])+max([0, 1+Arg_1-Arg_2])+max([0, 1+-2*Arg_2+2*Arg_1]) {O(n)} 6: evalaaron2bb3in->evalaaron2bb4in: max([0, 1+Arg_1-Arg_2]) {O(n)} 7: evalaaron2bb3in->evalaaron2bb4in: max([0, 1+Arg_1-Arg_2]) {O(n)} 8: evalaaron2bb3in->evalaaron2bb5in: max([0, 1+Arg_1-Arg_2]) {O(n)} 9: evalaaron2bb4in->evalaaron2bb6in: max([0, 1+-2*Arg_2+2*Arg_1]) {O(n)} 10: evalaaron2bb5in->evalaaron2bb6in: max([0, 1+Arg_1-Arg_2]) {O(n)} 3: evalaaron2bb6in->evalaaron2returnin: 1 {O(1)} 5: evalaaron2bb6in->evalaaron2bb3in: max([0, 1+Arg_1-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: Arg_2 {O(n)} 6: evalaaron2bb3in->evalaaron2bb4in, Arg_2: min([0, Arg_1])-max([0, (1+-2*Arg_2+2*Arg_1)*max([1, 1+Arg_0])]) {O(n^2)} 7: evalaaron2bb3in->evalaaron2bb4in, Arg_0: 0 {O(1)} 7: evalaaron2bb3in->evalaaron2bb4in, Arg_1: Arg_2 {O(n)} 7: evalaaron2bb3in->evalaaron2bb4in, Arg_2: min([0, Arg_1])-max([0, (1+-2*Arg_2+2*Arg_1)*max([1, 1+Arg_0])]) {O(n^2)} 8: evalaaron2bb3in->evalaaron2bb5in, Arg_0: 0 {O(1)} 8: evalaaron2bb3in->evalaaron2bb5in, Arg_1: Arg_2 {O(n)} 8: evalaaron2bb3in->evalaaron2bb5in, Arg_2: min([0, Arg_1])-max([0, (1+-2*Arg_2+2*Arg_1)*max([1, 1+Arg_0])]) {O(n^2)} 9: evalaaron2bb4in->evalaaron2bb6in, Arg_0: 0 {O(1)} 9: evalaaron2bb4in->evalaaron2bb6in, Arg_1: Arg_2 {O(n)} 9: evalaaron2bb4in->evalaaron2bb6in, Arg_2: min([0, Arg_1])-max([0, (1+-2*Arg_2+2*Arg_1)*max([1, 1+Arg_0])]) {O(n^2)} 10: evalaaron2bb5in->evalaaron2bb6in, Arg_0: 0 {O(1)} 10: evalaaron2bb5in->evalaaron2bb6in, Arg_1: Arg_2 {O(n)} 10: evalaaron2bb5in->evalaaron2bb6in, Arg_2: min([0, Arg_1])-max([0, (1+-2*Arg_2+2*Arg_1)*max([1, 1+Arg_0])]) {O(n^2)} 3: evalaaron2bb6in->evalaaron2returnin, Arg_0: 0 {O(1)} 3: evalaaron2bb6in->evalaaron2returnin, Arg_1: Arg_2 {O(n)} 3: evalaaron2bb6in->evalaaron2returnin, Arg_2: min([Arg_1, -(max([0, -(Arg_1)])+max([0, (1+-2*Arg_2+2*Arg_1)*max([1, 1+Arg_0])]))]) {O(n^2)} 5: evalaaron2bb6in->evalaaron2bb3in, Arg_0: 0 {O(1)} 5: evalaaron2bb6in->evalaaron2bb3in, Arg_1: Arg_2 {O(n)} 5: evalaaron2bb6in->evalaaron2bb3in, Arg_2: min([0, Arg_1])-max([0, (1+-2*Arg_2+2*Arg_1)*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([Arg_1, Arg_2]) {O(n)} 11: evalaaron2returnin->evalaaron2stop, Arg_2: min([Arg_2, min([Arg_1, -(max([0, -(Arg_1)])+max([0, (1+-2*Arg_2+2*Arg_1)*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, (1+Arg_1-Arg_2)*max([1, 1+Arg_0])]) {O(n^2)} 6: evalaaron2bb3in->evalaaron2bb4in, Arg_2: Arg_1 {O(n)} 7: evalaaron2bb3in->evalaaron2bb4in, Arg_0: Arg_0 {O(n)} 7: evalaaron2bb3in->evalaaron2bb4in, Arg_1: max([Arg_2, Arg_0])+max([0, (1+Arg_1-Arg_2)*max([1, 1+Arg_0])]) {O(n^2)} 7: evalaaron2bb3in->evalaaron2bb4in, Arg_2: Arg_1 {O(n)} 8: evalaaron2bb3in->evalaaron2bb5in, Arg_0: Arg_0 {O(n)} 8: evalaaron2bb3in->evalaaron2bb5in, Arg_1: max([Arg_2, Arg_0])+max([0, (1+Arg_1-Arg_2)*max([1, 1+Arg_0])]) {O(n^2)} 8: evalaaron2bb3in->evalaaron2bb5in, Arg_2: Arg_1 {O(n)} 9: evalaaron2bb4in->evalaaron2bb6in, Arg_0: Arg_0 {O(n)} 9: evalaaron2bb4in->evalaaron2bb6in, Arg_1: max([Arg_2, Arg_0])+max([0, (1+Arg_1-Arg_2)*max([1, 1+Arg_0])]) {O(n^2)} 9: evalaaron2bb4in->evalaaron2bb6in, Arg_2: Arg_1 {O(n)} 10: evalaaron2bb5in->evalaaron2bb6in, Arg_0: Arg_0 {O(n)} 10: evalaaron2bb5in->evalaaron2bb6in, Arg_1: max([Arg_2, Arg_0])+max([0, (1+Arg_1-Arg_2)*max([1, 1+Arg_0])]) {O(n^2)} 10: evalaaron2bb5in->evalaaron2bb6in, Arg_2: Arg_1 {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, (1+Arg_1-Arg_2)*max([1, 1+Arg_0])])]) {O(n^2)} 3: evalaaron2bb6in->evalaaron2returnin, Arg_2: Arg_1 {O(n)} 5: evalaaron2bb6in->evalaaron2bb3in, Arg_0: Arg_0 {O(n)} 5: evalaaron2bb6in->evalaaron2bb3in, Arg_1: max([Arg_2, Arg_0])+max([0, (1+Arg_1-Arg_2)*max([1, 1+Arg_0])]) {O(n^2)} 5: evalaaron2bb6in->evalaaron2bb3in, Arg_2: Arg_1 {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_1, max([Arg_2, max([Arg_2, Arg_0])+max([0, (1+Arg_1-Arg_2)*max([1, 1+Arg_0])])])]) {O(n^2)} 11: evalaaron2returnin->evalaaron2stop, Arg_2: max([Arg_2, Arg_1]) {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(10 + 5 * Arg_1 + -5 * Arg_2, 5) + nat(1 + 2 * Arg_1 + -2 * Arg_2)) ---------------------------------------- (3) Loat Proof (FINISHED) ### Pre-processing the ITS problem ### Initial linear ITS problem Start location: evalaaron2start 0: evalaaron2start -> evalaaron2entryin : [], cost: 1 1: evalaaron2entryin -> evalaaron2bb6in : B'=C, C'=B, [ A>=0 ], cost: 1 2: evalaaron2entryin -> evalaaron2returnin : [ 0>=1+A ], cost: 1 3: evalaaron2bb6in -> evalaaron2returnin : [ B>=1+C ], cost: 1 4: evalaaron2bb6in -> evalaaron2returnin : [ 0>=1+A ], cost: 1 5: evalaaron2bb6in -> evalaaron2bb3in : [ C>=B && A>=0 ], cost: 1 6: evalaaron2bb3in -> evalaaron2bb4in : [ 0>=1+free ], cost: 1 7: evalaaron2bb3in -> evalaaron2bb4in : [ free_1>=1 ], cost: 1 8: evalaaron2bb3in -> evalaaron2bb5in : [], cost: 1 9: evalaaron2bb4in -> evalaaron2bb6in : C'=-1+C-A, [], cost: 1 10: evalaaron2bb5in -> evalaaron2bb6in : B'=1+A+B, [], cost: 1 11: evalaaron2returnin -> evalaaron2stop : [], cost: 1 Removed unreachable and leaf rules: Start location: evalaaron2start 0: evalaaron2start -> evalaaron2entryin : [], cost: 1 1: evalaaron2entryin -> evalaaron2bb6in : B'=C, C'=B, [ A>=0 ], cost: 1 5: evalaaron2bb6in -> evalaaron2bb3in : [ C>=B && A>=0 ], cost: 1 6: evalaaron2bb3in -> evalaaron2bb4in : [ 0>=1+free ], cost: 1 7: evalaaron2bb3in -> evalaaron2bb4in : [ free_1>=1 ], cost: 1 8: evalaaron2bb3in -> evalaaron2bb5in : [], cost: 1 9: evalaaron2bb4in -> evalaaron2bb6in : C'=-1+C-A, [], cost: 1 10: evalaaron2bb5in -> evalaaron2bb6in : B'=1+A+B, [], cost: 1 Simplified all rules, resulting in: Start location: evalaaron2start 0: evalaaron2start -> evalaaron2entryin : [], cost: 1 1: evalaaron2entryin -> evalaaron2bb6in : B'=C, C'=B, [ A>=0 ], cost: 1 5: evalaaron2bb6in -> evalaaron2bb3in : [ C>=B && A>=0 ], cost: 1 7: evalaaron2bb3in -> evalaaron2bb4in : [], cost: 1 8: evalaaron2bb3in -> evalaaron2bb5in : [], cost: 1 9: evalaaron2bb4in -> evalaaron2bb6in : C'=-1+C-A, [], cost: 1 10: evalaaron2bb5in -> evalaaron2bb6in : B'=1+A+B, [], cost: 1 ### Simplification by acceleration and chaining ### Eliminated locations (on linear paths): Start location: evalaaron2start 12: evalaaron2start -> evalaaron2bb6in : B'=C, C'=B, [ A>=0 ], cost: 2 5: evalaaron2bb6in -> evalaaron2bb3in : [ C>=B && A>=0 ], cost: 1 13: evalaaron2bb3in -> evalaaron2bb6in : C'=-1+C-A, [], cost: 2 14: evalaaron2bb3in -> evalaaron2bb6in : B'=1+A+B, [], cost: 2 Eliminated locations (on tree-shaped paths): Start location: evalaaron2start 12: evalaaron2start -> evalaaron2bb6in : B'=C, C'=B, [ A>=0 ], cost: 2 15: evalaaron2bb6in -> evalaaron2bb6in : C'=-1+C-A, [ C>=B && A>=0 ], cost: 3 16: evalaaron2bb6in -> evalaaron2bb6in : B'=1+A+B, [ C>=B && A>=0 ], cost: 3 Accelerating simple loops of location 2. Accelerating the following rules: 15: evalaaron2bb6in -> evalaaron2bb6in : C'=-1+C-A, [ C>=B && A>=0 ], cost: 3 16: evalaaron2bb6in -> evalaaron2bb6in : B'=1+A+B, [ C>=B && A>=0 ], cost: 3 Accelerated rule 15 with backward acceleration, yielding the new rule 17. Accelerated rule 16 with backward acceleration, yielding the new rule 18. Removing the simple loops: 15 16. Accelerated all simple loops using metering functions (where possible): Start location: evalaaron2start 12: evalaaron2start -> evalaaron2bb6in : B'=C, C'=B, [ A>=0 ], cost: 2 17: evalaaron2bb6in -> evalaaron2bb6in : C'=C-A*k-k, [ C>=B && A>=0 && k>0 && 1+C-A*(-1+k)-k>=B ], cost: 3*k 18: evalaaron2bb6in -> evalaaron2bb6in : B'=A*k_1+k_1+B, [ C>=B && A>=0 && k_1>0 && C>=-1+k_1+(-1+k_1)*A+B ], cost: 3*k_1 Chained accelerated rules (with incoming rules): Start location: evalaaron2start 12: evalaaron2start -> evalaaron2bb6in : B'=C, C'=B, [ A>=0 ], cost: 2 19: evalaaron2start -> evalaaron2bb6in : B'=C, C'=-A*k-k+B, [ A>=0 && B>=C && k>0 && 1-A*(-1+k)-k+B>=C ], cost: 2+3*k 20: evalaaron2start -> evalaaron2bb6in : B'=C+A*k_1+k_1, C'=B, [ A>=0 && B>=C && k_1>0 && B>=-1+C+k_1+(-1+k_1)*A ], cost: 2+3*k_1 Removed unreachable locations (and leaf rules with constant cost): Start location: evalaaron2start 19: evalaaron2start -> evalaaron2bb6in : B'=C, C'=-A*k-k+B, [ A>=0 && B>=C && k>0 && 1-A*(-1+k)-k+B>=C ], cost: 2+3*k 20: evalaaron2start -> evalaaron2bb6in : B'=C+A*k_1+k_1, C'=B, [ A>=0 && B>=C && k_1>0 && B>=-1+C+k_1+(-1+k_1)*A ], cost: 2+3*k_1 ### Computing asymptotic complexity ### Fully simplified ITS problem Start location: evalaaron2start 19: evalaaron2start -> evalaaron2bb6in : B'=C, C'=-A*k-k+B, [ A>=0 && B>=C && k>0 && 1-A*(-1+k)-k+B>=C ], cost: 2+3*k 20: evalaaron2start -> evalaaron2bb6in : B'=C+A*k_1+k_1, C'=B, [ A>=0 && B>=C && k_1>0 && B>=-1+C+k_1+(-1+k_1)*A ], cost: 2+3*k_1 Computing asymptotic complexity for rule 19 Solved the limit problem by the following transformations: Created initial limit problem: 2-C-A*(-1+k)-k+B (+/+!), 1-C+B (+/+!), 2+3*k (+), k (+/+!), 1+A (+/+!) [not solved] removing all constraints (solved by SMT) resulting limit problem: [solved] applying transformation rule (C) using substitution {C==0,A==0,k==n,B==2*n} resulting limit problem: [solved] Solved the limit problem by the following transformations: Created initial limit problem: 2-C-A*(-1+k)-k+B (+/+!), 1-C+B (+/+!), 2+3*k (+), k (+/+!), 1+A (+/+!) [not solved] applying transformation rule (C) using substitution {A==0} resulting limit problem: 1 (+/+!), 1-C+B (+/+!), 2+3*k (+), 2-C-k+B (+/+!), k (+/+!) [not solved] applying transformation rule (C) using substitution {C==1-A*(-1+k)-k+B} resulting limit problem: 1 (+/+!), 2+3*k (+), A*(-1+k)+k (+/+!), k (+/+!), 1+A*(-1+k) (+/+!) [not solved] applying transformation rule (B), deleting 1 (+/+!) resulting limit problem: 2+3*k (+), A*(-1+k)+k (+/+!), k (+/+!), 1+A*(-1+k) (+/+!) [not solved] removing all constraints (solved by SMT) resulting limit problem: [solved] applying transformation rule (C) using substitution {A==1,k==n} resulting limit problem: [solved] Solved the limit problem by the following transformations: Created initial limit problem: 2-C-A*(-1+k)-k+B (+/+!), 1-C+B (+/+!), 2+3*k (+), k (+/+!), 1+A (+/+!) [not solved] applying transformation rule (C) using substitution {C==1-A*(-1+k)-k+B} resulting limit problem: 1 (+/+!), 2+3*k (+), A*(-1+k)+k (+/+!), k (+/+!), 1+A (+/+!) [not solved] applying transformation rule (B), deleting 1 (+/+!) resulting limit problem: 2+3*k (+), A*(-1+k)+k (+/+!), k (+/+!), 1+A (+/+!) [not solved] removing all constraints (solved by SMT) resulting limit problem: [solved] applying transformation rule (C) using substitution {A==0,k==n} resulting limit problem: [solved] Solved the limit problem by the following transformations: Created initial limit problem: 2-C-A*(-1+k)-k+B (+/+!), 1-C+B (+/+!), 2+3*k (+), k (+/+!), 1+A (+/+!) [not solved] applying transformation rule (C) using substitution {A==0} resulting limit problem: 1 (+/+!), 1-C+B (+/+!), 2+3*k (+), 2-C-k+B (+/+!), k (+/+!) [not solved] applying transformation rule (B), deleting 1 (+/+!) resulting limit problem: 1-C+B (+/+!), 2+3*k (+), 2-C-k+B (+/+!), k (+/+!) [not solved] removing all constraints (solved by SMT) resulting limit problem: [solved] applying transformation rule (C) using substitution {C==0,k==n,B==n} resulting limit problem: [solved] Solution: C / 0 A / 0 k / n B / 2*n Resulting cost 2+3*n has complexity: Poly(n^1) Found new complexity Poly(n^1). Computing asymptotic complexity for rule 20 Solved the limit problem by the following transformations: Created initial limit problem: 1-C+B (+/+!), 2-C-k_1-(-1+k_1)*A+B (+/+!), k_1 (+/+!), 2+3*k_1 (+), 1+A (+/+!) [not solved] removing all constraints (solved by SMT) resulting limit problem: [solved] applying transformation rule (C) using substitution {C==0,A==0,k_1==n,B==2*n} resulting limit problem: [solved] Solved the limit problem by the following transformations: Created initial limit problem: 1-C+B (+/+!), 2-C-k_1-(-1+k_1)*A+B (+/+!), k_1 (+/+!), 2+3*k_1 (+), 1+A (+/+!) [not solved] applying transformation rule (C) using substitution {A==0} resulting limit problem: 1 (+/+!), 1-C+B (+/+!), 2-C-k_1+B (+/+!), k_1 (+/+!), 2+3*k_1 (+) [not solved] applying transformation rule (C) using substitution {B==-1+C+k_1+(-1+k_1)*A} resulting limit problem: 1 (+/+!), k_1+(-1+k_1)*A (+/+!), 1+(-1+k_1)*A (+/+!), k_1 (+/+!), 2+3*k_1 (+) [not solved] applying transformation rule (B), deleting 1 (+/+!) resulting limit problem: k_1+(-1+k_1)*A (+/+!), 1+(-1+k_1)*A (+/+!), k_1 (+/+!), 2+3*k_1 (+) [not solved] removing all constraints (solved by SMT) resulting limit problem: [solved] applying transformation rule (C) using substitution {A==1,k_1==n} resulting limit problem: [solved] Solved the limit problem by the following transformations: Created initial limit problem: 1-C+B (+/+!), 2-C-k_1-(-1+k_1)*A+B (+/+!), k_1 (+/+!), 2+3*k_1 (+), 1+A (+/+!) [not solved] applying transformation rule (C) using substitution {B==-1+C+k_1+(-1+k_1)*A} resulting limit problem: 1 (+/+!), k_1+(-1+k_1)*A (+/+!), k_1 (+/+!), 2+3*k_1 (+), 1+A (+/+!) [not solved] applying transformation rule (B), deleting 1 (+/+!) resulting limit problem: k_1+(-1+k_1)*A (+/+!), k_1 (+/+!), 2+3*k_1 (+), 1+A (+/+!) [not solved] removing all constraints (solved by SMT) resulting limit problem: [solved] applying transformation rule (C) using substitution {A==0,k_1==n} resulting limit problem: [solved] Solved the limit problem by the following transformations: Created initial limit problem: 1-C+B (+/+!), 2-C-k_1-(-1+k_1)*A+B (+/+!), k_1 (+/+!), 2+3*k_1 (+), 1+A (+/+!) [not solved] applying transformation rule (C) using substitution {A==0} resulting limit problem: 1 (+/+!), 1-C+B (+/+!), 2-C-k_1+B (+/+!), k_1 (+/+!), 2+3*k_1 (+) [not solved] applying transformation rule (B), deleting 1 (+/+!) resulting limit problem: 1-C+B (+/+!), 2-C-k_1+B (+/+!), k_1 (+/+!), 2+3*k_1 (+) [not solved] removing all constraints (solved by SMT) resulting limit problem: [solved] applying transformation rule (C) using substitution {C==0,k_1==n,B==n} resulting limit problem: [solved] Solution: C / 0 A / 0 k_1 / n B / 2*n Resulting cost 2+3*n has 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+3*n Rule cost: 2+3*k Rule guard: [ A>=0 && B>=C && k>0 && 1-A*(-1+k)-k+B>=C ] WORST_CASE(Omega(n^1),?) ---------------------------------------- (4) BOUNDS(n^1, INF)