/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), ?) proof of /export/starexec/sandbox2/benchmark/theBenchmark.koat # AProVE Commit ID: 794c25de1cacf0d048858bcd21c9a779e1221865 marcel 20200619 unpublished dirty The runtime complexity of the given CpxIntTrs could be proven to be BOUNDS(n^1, INF). (0) CpxIntTrs (1) Loat Proof [FINISHED, 3352 ms] (2) BOUNDS(n^1, INF) ---------------------------------------- (0) Obligation: Complexity Int TRS consisting of the following rules: eval_rank2_start(v_10, v_14, v_15, v_16, v_5, v_m, v_x_0, v_x_1, v_x_2, v_y_0, v_y_1, v_y_2) -> Com_1(eval_rank2_bb0_in(v_10, v_14, v_15, v_16, v_5, v_m, v_x_0, v_x_1, v_x_2, v_y_0, v_y_1, v_y_2)) :|: TRUE eval_rank2_bb0_in(v_10, v_14, v_15, v_16, v_5, v_m, v_x_0, v_x_1, v_x_2, v_y_0, v_y_1, v_y_2) -> Com_1(eval_rank2_0(v_10, v_14, v_15, v_16, v_5, v_m, v_x_0, v_x_1, v_x_2, v_y_0, v_y_1, v_y_2)) :|: TRUE eval_rank2_0(v_10, v_14, v_15, v_16, v_5, v_m, v_x_0, v_x_1, v_x_2, v_y_0, v_y_1, v_y_2) -> Com_1(eval_rank2_1(v_10, v_14, v_15, v_16, v_5, v_m, v_x_0, v_x_1, v_x_2, v_y_0, v_y_1, v_y_2)) :|: TRUE eval_rank2_1(v_10, v_14, v_15, v_16, v_5, v_m, v_x_0, v_x_1, v_x_2, v_y_0, v_y_1, v_y_2) -> Com_1(eval_rank2_2(v_10, v_14, v_15, v_16, v_5, v_m, v_x_0, v_x_1, v_x_2, v_y_0, v_y_1, v_y_2)) :|: TRUE eval_rank2_2(v_10, v_14, v_15, v_16, v_5, v_m, v_x_0, v_x_1, v_x_2, v_y_0, v_y_1, v_y_2) -> Com_1(eval_rank2_3(v_10, v_14, v_15, v_16, v_5, v_m, v_x_0, v_x_1, v_x_2, v_y_0, v_y_1, v_y_2)) :|: TRUE eval_rank2_3(v_10, v_14, v_15, v_16, v_5, v_m, v_x_0, v_x_1, v_x_2, v_y_0, v_y_1, v_y_2) -> Com_1(eval_rank2_4(v_10, v_14, v_15, v_16, v_5, v_m, v_x_0, v_x_1, v_x_2, v_y_0, v_y_1, v_y_2)) :|: TRUE eval_rank2_4(v_10, v_14, v_15, v_16, v_5, v_m, v_x_0, v_x_1, v_x_2, v_y_0, v_y_1, v_y_2) -> Com_1(eval_rank2_5(v_10, v_14, v_15, v_16, v_5, v_m, v_x_0, v_x_1, v_x_2, v_y_0, v_y_1, v_y_2)) :|: TRUE eval_rank2_5(v_10, v_14, v_15, v_16, v_5, v_m, v_x_0, v_x_1, v_x_2, v_y_0, v_y_1, v_y_2) -> Com_1(eval_rank2_6(v_10, v_14, v_15, v_16, v_5, v_m, v_x_0, v_x_1, v_x_2, v_y_0, v_y_1, v_y_2)) :|: TRUE eval_rank2_6(v_10, v_14, v_15, v_16, v_5, v_m, v_x_0, v_x_1, v_x_2, v_y_0, v_y_1, v_y_2) -> Com_1(eval_rank2_7(v_10, v_14, v_15, v_16, v_5, v_m, v_x_0, v_x_1, v_x_2, v_y_0, v_y_1, v_y_2)) :|: TRUE eval_rank2_7(v_10, v_14, v_15, v_16, v_5, v_m, v_x_0, v_x_1, v_x_2, v_y_0, v_y_1, v_y_2) -> Com_1(eval_rank2_8(v_10, v_14, v_15, v_16, v_5, v_m, v_x_0, v_x_1, v_x_2, v_y_0, v_y_1, v_y_2)) :|: TRUE eval_rank2_8(v_10, v_14, v_15, v_16, v_5, v_m, v_x_0, v_x_1, v_x_2, v_y_0, v_y_1, v_y_2) -> Com_1(eval_rank2_bb1_in(v_10, v_14, v_15, v_16, v_5, v_m, v_m, v_x_1, v_x_2, v_m, v_y_1, v_y_2)) :|: TRUE eval_rank2_bb1_in(v_10, v_14, v_15, v_16, v_5, v_m, v_x_0, v_x_1, v_x_2, v_y_0, v_y_1, v_y_2) -> Com_1(eval_rank2_bb2_in(v_10, v_14, v_15, v_16, v_5, v_m, v_x_0, v_x_1, v_x_2, v_y_0, v_y_1, v_y_2)) :|: v_x_0 >= 2 eval_rank2_bb1_in(v_10, v_14, v_15, v_16, v_5, v_m, v_x_0, v_x_1, v_x_2, v_y_0, v_y_1, v_y_2) -> Com_1(eval_rank2_bb9_in(v_10, v_14, v_15, v_16, v_5, v_m, v_x_0, v_x_1, v_x_2, v_y_0, v_y_1, v_y_2)) :|: v_x_0 < 2 eval_rank2_bb2_in(v_10, v_14, v_15, v_16, v_5, v_m, v_x_0, v_x_1, v_x_2, v_y_0, v_y_1, v_y_2) -> Com_1(eval_rank2_bb3_in(v_10, v_14, v_15, v_16, v_5, v_m, v_x_0, v_x_0 - 1, v_x_2, v_y_0, v_y_0 + v_x_0 - 1, v_y_2)) :|: TRUE eval_rank2_bb3_in(v_10, v_14, v_15, v_16, v_5, v_m, v_x_0, v_x_1, v_x_2, v_y_0, v_y_1, v_y_2) -> Com_1(eval_rank2_bb4_in(v_10, v_14, v_15, v_16, v_5, v_m, v_x_0, v_x_1, v_x_2, v_y_0, v_y_1, v_y_2)) :|: v_y_1 >= v_x_1 + 1 eval_rank2_bb3_in(v_10, v_14, v_15, v_16, v_5, v_m, v_x_0, v_x_1, v_x_2, v_y_0, v_y_1, v_y_2) -> Com_1(eval_rank2__critedge_in(v_10, v_14, v_15, v_16, v_5, v_m, v_x_0, v_x_1, v_x_2, v_y_0, v_y_1, v_y_2)) :|: v_y_1 < v_x_1 + 1 eval_rank2_bb4_in(v_10, v_14, v_15, v_16, v_5, v_m, v_x_0, v_x_1, v_x_2, v_y_0, v_y_1, v_y_2) -> Com_1(eval_rank2_14(v_10, v_14, v_15, v_16, v_5, v_m, v_x_0, v_x_1, v_x_2, v_y_0, v_y_1, v_y_2)) :|: TRUE eval_rank2_14(v_10, v_14, v_15, v_16, v_5, v_m, v_x_0, v_x_1, v_x_2, v_y_0, v_y_1, v_y_2) -> Com_1(eval_rank2_15(v_10, v_14, v_15, v_16, nondef_0, v_m, v_x_0, v_x_1, v_x_2, v_y_0, v_y_1, v_y_2)) :|: TRUE eval_rank2_15(v_10, v_14, v_15, v_16, v_5, v_m, v_x_0, v_x_1, v_x_2, v_y_0, v_y_1, v_y_2) -> Com_1(eval_rank2_bb5_in(v_10, v_14, v_15, v_16, v_5, v_m, v_x_0, v_x_1, v_x_2, v_y_0, v_y_1, v_y_2)) :|: v_5 > 0 eval_rank2_15(v_10, v_14, v_15, v_16, v_5, v_m, v_x_0, v_x_1, v_x_2, v_y_0, v_y_1, v_y_2) -> Com_1(eval_rank2__critedge_in(v_10, v_14, v_15, v_16, v_5, v_m, v_x_0, v_x_1, v_x_2, v_y_0, v_y_1, v_y_2)) :|: v_5 <= 0 eval_rank2_bb5_in(v_10, v_14, v_15, v_16, v_5, v_m, v_x_0, v_x_1, v_x_2, v_y_0, v_y_1, v_y_2) -> Com_1(eval_rank2_bb6_in(v_10, v_14, v_15, v_16, v_5, v_m, v_x_0, v_x_1, v_x_1, v_y_0, v_y_1, v_y_1 - 1)) :|: TRUE eval_rank2_bb6_in(v_10, v_14, v_15, v_16, v_5, v_m, v_x_0, v_x_1, v_x_2, v_y_0, v_y_1, v_y_2) -> Com_1(eval_rank2_bb7_in(v_10, v_14, v_15, v_16, v_5, v_m, v_x_0, v_x_1, v_x_2, v_y_0, v_y_1, v_y_2)) :|: v_y_2 >= v_x_2 + 3 eval_rank2_bb6_in(v_10, v_14, v_15, v_16, v_5, v_m, v_x_0, v_x_1, v_x_2, v_y_0, v_y_1, v_y_2) -> Com_1(eval_rank2__critedge1_in(v_10, v_14, v_15, v_16, v_5, v_m, v_x_0, v_x_1, v_x_2, v_y_0, v_y_1, v_y_2)) :|: v_y_2 < v_x_2 + 3 eval_rank2_bb7_in(v_10, v_14, v_15, v_16, v_5, v_m, v_x_0, v_x_1, v_x_2, v_y_0, v_y_1, v_y_2) -> Com_1(eval_rank2_20(v_10, v_14, v_15, v_16, v_5, v_m, v_x_0, v_x_1, v_x_2, v_y_0, v_y_1, v_y_2)) :|: TRUE eval_rank2_20(v_10, v_14, v_15, v_16, v_5, v_m, v_x_0, v_x_1, v_x_2, v_y_0, v_y_1, v_y_2) -> Com_1(eval_rank2_21(nondef_1, v_14, v_15, v_16, v_5, v_m, v_x_0, v_x_1, v_x_2, v_y_0, v_y_1, v_y_2)) :|: TRUE eval_rank2_21(v_10, v_14, v_15, v_16, v_5, v_m, v_x_0, v_x_1, v_x_2, v_y_0, v_y_1, v_y_2) -> Com_1(eval_rank2_bb8_in(v_10, v_14, v_15, v_16, v_5, v_m, v_x_0, v_x_1, v_x_2, v_y_0, v_y_1, v_y_2)) :|: v_10 > 0 eval_rank2_21(v_10, v_14, v_15, v_16, v_5, v_m, v_x_0, v_x_1, v_x_2, v_y_0, v_y_1, v_y_2) -> Com_1(eval_rank2__critedge1_in(v_10, v_14, v_15, v_16, v_5, v_m, v_x_0, v_x_1, v_x_2, v_y_0, v_y_1, v_y_2)) :|: v_10 <= 0 eval_rank2_bb8_in(v_10, v_14, v_15, v_16, v_5, v_m, v_x_0, v_x_1, v_x_2, v_y_0, v_y_1, v_y_2) -> Com_1(eval_rank2_bb6_in(v_10, v_14, v_15, v_16, v_5, v_m, v_x_0, v_x_1, v_x_2 + 1, v_y_0, v_y_1, v_y_2 - 2)) :|: TRUE eval_rank2__critedge1_in(v_10, v_14, v_15, v_16, v_5, v_m, v_x_0, v_x_1, v_x_2, v_y_0, v_y_1, v_y_2) -> Com_1(eval_rank2_26(v_10, v_y_2 - 1, v_15, v_16, v_5, v_m, v_x_0, v_x_1, v_x_2, v_y_0, v_y_1, v_y_2)) :|: TRUE eval_rank2_26(v_10, v_14, v_15, v_16, v_5, v_m, v_x_0, v_x_1, v_x_2, v_y_0, v_y_1, v_y_2) -> Com_1(eval_rank2_27(v_10, v_14, v_15, v_16, v_5, v_m, v_x_0, v_x_1, v_x_2, v_y_0, v_y_1, v_y_2)) :|: TRUE eval_rank2_27(v_10, v_14, v_15, v_16, v_5, v_m, v_x_0, v_x_1, v_x_2, v_y_0, v_y_1, v_y_2) -> Com_1(eval_rank2_bb3_in(v_10, v_14, v_15, v_16, v_5, v_m, v_x_0, v_x_2, v_x_2, v_y_0, v_14, v_y_2)) :|: TRUE eval_rank2__critedge_in(v_10, v_14, v_15, v_16, v_5, v_m, v_x_0, v_x_1, v_x_2, v_y_0, v_y_1, v_y_2) -> Com_1(eval_rank2_29(v_10, v_14, v_x_1 - 1, v_16, v_5, v_m, v_x_0, v_x_1, v_x_2, v_y_0, v_y_1, v_y_2)) :|: TRUE eval_rank2_29(v_10, v_14, v_15, v_16, v_5, v_m, v_x_0, v_x_1, v_x_2, v_y_0, v_y_1, v_y_2) -> Com_1(eval_rank2_30(v_10, v_14, v_15, v_16, v_5, v_m, v_x_0, v_x_1, v_x_2, v_y_0, v_y_1, v_y_2)) :|: TRUE eval_rank2_30(v_10, v_14, v_15, v_16, v_5, v_m, v_x_0, v_x_1, v_x_2, v_y_0, v_y_1, v_y_2) -> Com_1(eval_rank2_31(v_10, v_14, v_15, v_y_1 - v_15, v_5, v_m, v_x_0, v_x_1, v_x_2, v_y_0, v_y_1, v_y_2)) :|: TRUE eval_rank2_31(v_10, v_14, v_15, v_16, v_5, v_m, v_x_0, v_x_1, v_x_2, v_y_0, v_y_1, v_y_2) -> Com_1(eval_rank2_32(v_10, v_14, v_15, v_16, v_5, v_m, v_x_0, v_x_1, v_x_2, v_y_0, v_y_1, v_y_2)) :|: TRUE eval_rank2_32(v_10, v_14, v_15, v_16, v_5, v_m, v_x_0, v_x_1, v_x_2, v_y_0, v_y_1, v_y_2) -> Com_1(eval_rank2_bb1_in(v_10, v_14, v_15, v_16, v_5, v_m, v_15, v_x_1, v_x_2, v_16, v_y_1, v_y_2)) :|: TRUE eval_rank2_bb9_in(v_10, v_14, v_15, v_16, v_5, v_m, v_x_0, v_x_1, v_x_2, v_y_0, v_y_1, v_y_2) -> Com_1(eval_rank2_stop(v_10, v_14, v_15, v_16, v_5, v_m, v_x_0, v_x_1, v_x_2, v_y_0, v_y_1, v_y_2)) :|: TRUE The start-symbols are:[eval_rank2_start_12] ---------------------------------------- (1) Loat Proof (FINISHED) ### Pre-processing the ITS problem ### Initial linear ITS problem Start location: evalrank2start 0: evalrank2start -> evalrank2bb0in : [], cost: 1 1: evalrank2bb0in -> evalrank20 : [], cost: 1 2: evalrank20 -> evalrank21 : [], cost: 1 3: evalrank21 -> evalrank22 : [], cost: 1 4: evalrank22 -> evalrank23 : [], cost: 1 5: evalrank23 -> evalrank24 : [], cost: 1 6: evalrank24 -> evalrank25 : [], cost: 1 7: evalrank25 -> evalrank26 : [], cost: 1 8: evalrank26 -> evalrank27 : [], cost: 1 9: evalrank27 -> evalrank28 : [], cost: 1 10: evalrank28 -> evalrank2bb1in : A'=B, C'=B, [], cost: 1 11: evalrank2bb1in -> evalrank2bb2in : [ A>=2 ], cost: 1 12: evalrank2bb1in -> evalrank2bb9in : [ 1>=A ], cost: 1 13: evalrank2bb2in -> evalrank2bb3in : D'=-1+A, E'=-1+C+A, [], cost: 1 14: evalrank2bb3in -> evalrank2bb4in : [ E>=1+D ], cost: 1 15: evalrank2bb3in -> evalrank2critedgein : [ D>=E ], cost: 1 16: evalrank2bb4in -> evalrank214 : [], cost: 1 17: evalrank214 -> evalrank215 : F'=free, [], cost: 1 18: evalrank215 -> evalrank2bb5in : [ F>=1 ], cost: 1 19: evalrank215 -> evalrank2critedgein : [ 0>=F ], cost: 1 20: evalrank2bb5in -> evalrank2bb6in : G'=D, H'=-1+E, [], cost: 1 21: evalrank2bb6in -> evalrank2bb7in : [ H>=3+G ], cost: 1 22: evalrank2bb6in -> evalrank2critedge1in : [ 2+G>=H ], cost: 1 23: evalrank2bb7in -> evalrank220 : [], cost: 1 24: evalrank220 -> evalrank221 : Q'=free_1, [], cost: 1 25: evalrank221 -> evalrank2bb8in : [ Q>=1 ], cost: 1 26: evalrank221 -> evalrank2critedge1in : [ 0>=Q ], cost: 1 27: evalrank2bb8in -> evalrank2bb6in : G'=1+G, H'=-2+H, [], cost: 1 28: evalrank2critedge1in -> evalrank226 : J'=-1+H, [], cost: 1 29: evalrank226 -> evalrank227 : [], cost: 1 30: evalrank227 -> evalrank2bb3in : D'=G, E'=J, [], cost: 1 31: evalrank2critedgein -> evalrank229 : K'=-1+D, [], cost: 1 32: evalrank229 -> evalrank230 : [], cost: 1 33: evalrank230 -> evalrank231 : L'=-K+E, [], cost: 1 34: evalrank231 -> evalrank232 : [], cost: 1 35: evalrank232 -> evalrank2bb1in : A'=K, C'=L, [], cost: 1 36: evalrank2bb9in -> evalrank2stop : [], cost: 1 Checking for constant complexity: The following rule is satisfiable with cost >= 1, yielding constant complexity: 0: evalrank2start -> evalrank2bb0in : [], cost: 1 Removed unreachable and leaf rules: Start location: evalrank2start 0: evalrank2start -> evalrank2bb0in : [], cost: 1 1: evalrank2bb0in -> evalrank20 : [], cost: 1 2: evalrank20 -> evalrank21 : [], cost: 1 3: evalrank21 -> evalrank22 : [], cost: 1 4: evalrank22 -> evalrank23 : [], cost: 1 5: evalrank23 -> evalrank24 : [], cost: 1 6: evalrank24 -> evalrank25 : [], cost: 1 7: evalrank25 -> evalrank26 : [], cost: 1 8: evalrank26 -> evalrank27 : [], cost: 1 9: evalrank27 -> evalrank28 : [], cost: 1 10: evalrank28 -> evalrank2bb1in : A'=B, C'=B, [], cost: 1 11: evalrank2bb1in -> evalrank2bb2in : [ A>=2 ], cost: 1 13: evalrank2bb2in -> evalrank2bb3in : D'=-1+A, E'=-1+C+A, [], cost: 1 14: evalrank2bb3in -> evalrank2bb4in : [ E>=1+D ], cost: 1 15: evalrank2bb3in -> evalrank2critedgein : [ D>=E ], cost: 1 16: evalrank2bb4in -> evalrank214 : [], cost: 1 17: evalrank214 -> evalrank215 : F'=free, [], cost: 1 18: evalrank215 -> evalrank2bb5in : [ F>=1 ], cost: 1 19: evalrank215 -> evalrank2critedgein : [ 0>=F ], cost: 1 20: evalrank2bb5in -> evalrank2bb6in : G'=D, H'=-1+E, [], cost: 1 21: evalrank2bb6in -> evalrank2bb7in : [ H>=3+G ], cost: 1 22: evalrank2bb6in -> evalrank2critedge1in : [ 2+G>=H ], cost: 1 23: evalrank2bb7in -> evalrank220 : [], cost: 1 24: evalrank220 -> evalrank221 : Q'=free_1, [], cost: 1 25: evalrank221 -> evalrank2bb8in : [ Q>=1 ], cost: 1 26: evalrank221 -> evalrank2critedge1in : [ 0>=Q ], cost: 1 27: evalrank2bb8in -> evalrank2bb6in : G'=1+G, H'=-2+H, [], cost: 1 28: evalrank2critedge1in -> evalrank226 : J'=-1+H, [], cost: 1 29: evalrank226 -> evalrank227 : [], cost: 1 30: evalrank227 -> evalrank2bb3in : D'=G, E'=J, [], cost: 1 31: evalrank2critedgein -> evalrank229 : K'=-1+D, [], cost: 1 32: evalrank229 -> evalrank230 : [], cost: 1 33: evalrank230 -> evalrank231 : L'=-K+E, [], cost: 1 34: evalrank231 -> evalrank232 : [], cost: 1 35: evalrank232 -> evalrank2bb1in : A'=K, C'=L, [], cost: 1 ### Simplification by acceleration and chaining ### Eliminated locations (on linear paths): Start location: evalrank2start 46: evalrank2start -> evalrank2bb1in : A'=B, C'=B, [], cost: 11 47: evalrank2bb1in -> evalrank2bb3in : D'=-1+A, E'=-1+C+A, [ A>=2 ], cost: 2 15: evalrank2bb3in -> evalrank2critedgein : [ D>=E ], cost: 1 49: evalrank2bb3in -> evalrank215 : F'=free, [ E>=1+D ], cost: 3 19: evalrank215 -> evalrank2critedgein : [ 0>=F ], cost: 1 50: evalrank215 -> evalrank2bb6in : G'=D, H'=-1+E, [ F>=1 ], cost: 2 22: evalrank2bb6in -> evalrank2critedge1in : [ 2+G>=H ], cost: 1 52: evalrank2bb6in -> evalrank221 : Q'=free_1, [ H>=3+G ], cost: 3 26: evalrank221 -> evalrank2critedge1in : [ 0>=Q ], cost: 1 53: evalrank221 -> evalrank2bb6in : G'=1+G, H'=-2+H, [ Q>=1 ], cost: 2 55: evalrank2critedge1in -> evalrank2bb3in : D'=G, E'=-1+H, J'=-1+H, [], cost: 3 59: evalrank2critedgein -> evalrank2bb1in : A'=-1+D, C'=1-D+E, K'=-1+D, L'=1-D+E, [], cost: 5 Eliminated locations (on tree-shaped paths): Start location: evalrank2start 46: evalrank2start -> evalrank2bb1in : A'=B, C'=B, [], cost: 11 47: evalrank2bb1in -> evalrank2bb3in : D'=-1+A, E'=-1+C+A, [ A>=2 ], cost: 2 61: evalrank2bb3in -> evalrank2bb6in : F'=free, G'=D, H'=-1+E, [ E>=1+D && free>=1 ], cost: 5 62: evalrank2bb3in -> evalrank2bb1in : A'=-1+D, C'=1-D+E, K'=-1+D, L'=1-D+E, [ D>=E ], cost: 6 63: evalrank2bb3in -> evalrank2bb1in : A'=-1+D, C'=1-D+E, F'=free, K'=-1+D, L'=1-D+E, [ E>=1+D && 0>=free ], cost: 9 65: evalrank2bb6in -> evalrank2bb6in : G'=1+G, H'=-2+H, Q'=free_1, [ H>=3+G && free_1>=1 ], cost: 5 66: evalrank2bb6in -> evalrank2bb3in : D'=G, E'=-1+H, J'=-1+H, [ 2+G>=H ], cost: 4 67: evalrank2bb6in -> evalrank2bb3in : D'=G, E'=-1+H, Q'=free_1, J'=-1+H, [ H>=3+G && 0>=free_1 ], cost: 7 Accelerating simple loops of location 18. Accelerating the following rules: 65: evalrank2bb6in -> evalrank2bb6in : G'=1+G, H'=-2+H, Q'=free_1, [ H>=3+G && free_1>=1 ], cost: 5 Accelerated rule 65 with metering function meter (where 3*meter==-2-G+H), yielding the new rule 68. Removing the simple loops: 65. Accelerated all simple loops using metering functions (where possible): Start location: evalrank2start 46: evalrank2start -> evalrank2bb1in : A'=B, C'=B, [], cost: 11 47: evalrank2bb1in -> evalrank2bb3in : D'=-1+A, E'=-1+C+A, [ A>=2 ], cost: 2 61: evalrank2bb3in -> evalrank2bb6in : F'=free, G'=D, H'=-1+E, [ E>=1+D && free>=1 ], cost: 5 62: evalrank2bb3in -> evalrank2bb1in : A'=-1+D, C'=1-D+E, K'=-1+D, L'=1-D+E, [ D>=E ], cost: 6 63: evalrank2bb3in -> evalrank2bb1in : A'=-1+D, C'=1-D+E, F'=free, K'=-1+D, L'=1-D+E, [ E>=1+D && 0>=free ], cost: 9 66: evalrank2bb6in -> evalrank2bb3in : D'=G, E'=-1+H, J'=-1+H, [ 2+G>=H ], cost: 4 67: evalrank2bb6in -> evalrank2bb3in : D'=G, E'=-1+H, Q'=free_1, J'=-1+H, [ H>=3+G && 0>=free_1 ], cost: 7 68: evalrank2bb6in -> evalrank2bb6in : G'=G+meter, H'=H-2*meter, Q'=free_1, [ H>=3+G && free_1>=1 && 3*meter==-2-G+H && meter>=1 ], cost: 5*meter Chained accelerated rules (with incoming rules): Start location: evalrank2start 46: evalrank2start -> evalrank2bb1in : A'=B, C'=B, [], cost: 11 47: evalrank2bb1in -> evalrank2bb3in : D'=-1+A, E'=-1+C+A, [ A>=2 ], cost: 2 61: evalrank2bb3in -> evalrank2bb6in : F'=free, G'=D, H'=-1+E, [ E>=1+D && free>=1 ], cost: 5 62: evalrank2bb3in -> evalrank2bb1in : A'=-1+D, C'=1-D+E, K'=-1+D, L'=1-D+E, [ D>=E ], cost: 6 63: evalrank2bb3in -> evalrank2bb1in : A'=-1+D, C'=1-D+E, F'=free, K'=-1+D, L'=1-D+E, [ E>=1+D && 0>=free ], cost: 9 69: evalrank2bb3in -> evalrank2bb6in : F'=free, G'=D+meter, H'=-1+E-2*meter, Q'=free_1, [ free>=1 && -1+E>=3+D && free_1>=1 && 3*meter==-3-D+E && meter>=1 ], cost: 5+5*meter 66: evalrank2bb6in -> evalrank2bb3in : D'=G, E'=-1+H, J'=-1+H, [ 2+G>=H ], cost: 4 67: evalrank2bb6in -> evalrank2bb3in : D'=G, E'=-1+H, Q'=free_1, J'=-1+H, [ H>=3+G && 0>=free_1 ], cost: 7 Eliminated locations (on tree-shaped paths): Start location: evalrank2start 46: evalrank2start -> evalrank2bb1in : A'=B, C'=B, [], cost: 11 47: evalrank2bb1in -> evalrank2bb3in : D'=-1+A, E'=-1+C+A, [ A>=2 ], cost: 2 62: evalrank2bb3in -> evalrank2bb1in : A'=-1+D, C'=1-D+E, K'=-1+D, L'=1-D+E, [ D>=E ], cost: 6 63: evalrank2bb3in -> evalrank2bb1in : A'=-1+D, C'=1-D+E, F'=free, K'=-1+D, L'=1-D+E, [ E>=1+D && 0>=free ], cost: 9 70: evalrank2bb3in -> evalrank2bb3in : D'=D, E'=-2+E, F'=free, G'=D, H'=-1+E, J'=-2+E, [ E>=1+D && free>=1 && 2+D>=-1+E ], cost: 9 71: evalrank2bb3in -> evalrank2bb3in : D'=D, E'=-2+E, F'=free, G'=D, H'=-1+E, Q'=free_1, J'=-2+E, [ free>=1 && -1+E>=3+D && 0>=free_1 ], cost: 12 72: evalrank2bb3in -> evalrank2bb3in : D'=D+meter, E'=-2+E-2*meter, F'=free, G'=D+meter, H'=-1+E-2*meter, Q'=free_1, J'=-2+E-2*meter, [ free>=1 && -1+E>=3+D && free_1>=1 && 3*meter==-3-D+E && meter>=1 ], cost: 9+5*meter 73: evalrank2bb3in -> [34] : [ free>=1 && -1+E>=3+D && free_1>=1 && 3*meter==-3-D+E && meter>=1 ], cost: 5+5*meter Accelerating simple loops of location 13. Simplified some of the simple loops (and removed duplicate rules). Accelerating the following rules: 70: evalrank2bb3in -> evalrank2bb3in : E'=-2+E, F'=free, G'=D, H'=-1+E, J'=-2+E, [ E>=1+D && free>=1 && 2+D>=-1+E ], cost: 9 71: evalrank2bb3in -> evalrank2bb3in : E'=-2+E, F'=free, G'=D, H'=-1+E, Q'=free_1, J'=-2+E, [ free>=1 && -1+E>=3+D && 0>=free_1 ], cost: 12 72: evalrank2bb3in -> evalrank2bb3in : D'=D+meter, E'=-2+E-2*meter, F'=free, G'=D+meter, H'=-1+E-2*meter, Q'=free_1, J'=-2+E-2*meter, [ free>=1 && -1+E>=3+D && free_1>=1 && 3*meter==-3-D+E && meter>=1 ], cost: 9+5*meter Accelerated rule 70 with metering function meter_1 (where 2*meter_1==-D+E), yielding the new rule 74. Accelerated rule 71 with metering function meter_2 (where 2*meter_2==-3-D+E), yielding the new rule 75. During metering: Instantiating temporary variables by {meter==1} Accelerated rule 72 with metering function meter_3 (where 5*meter_3==-5-D+E), yielding the new rule 76. Nested simple loops 71 (outer loop) and 74 (inner loop) with metering function meter_4 (where 5*meter_4==-3-D-meter_1+E), resulting in the new rules: 77. During metering: Instantiating temporary variables by {meter_2==1} Removing the simple loops: 70 71 72. Accelerated all simple loops using metering functions (where possible): Start location: evalrank2start 46: evalrank2start -> evalrank2bb1in : A'=B, C'=B, [], cost: 11 47: evalrank2bb1in -> evalrank2bb3in : D'=-1+A, E'=-1+C+A, [ A>=2 ], cost: 2 62: evalrank2bb3in -> evalrank2bb1in : A'=-1+D, C'=1-D+E, K'=-1+D, L'=1-D+E, [ D>=E ], cost: 6 63: evalrank2bb3in -> evalrank2bb1in : A'=-1+D, C'=1-D+E, F'=free, K'=-1+D, L'=1-D+E, [ E>=1+D && 0>=free ], cost: 9 73: evalrank2bb3in -> [34] : [ free>=1 && -1+E>=3+D && free_1>=1 && 3*meter==-3-D+E && meter>=1 ], cost: 5+5*meter 74: evalrank2bb3in -> evalrank2bb3in : E'=-2*meter_1+E, F'=free, G'=D, H'=1-2*meter_1+E, J'=-2*meter_1+E, [ E>=1+D && free>=1 && 2+D>=-1+E && 2*meter_1==-D+E && meter_1>=1 ], cost: 9*meter_1 75: evalrank2bb3in -> evalrank2bb3in : E'=-2*meter_2+E, F'=free, G'=D, H'=1-2*meter_2+E, Q'=free_1, J'=-2*meter_2+E, [ free>=1 && -1+E>=3+D && 0>=free_1 && 2*meter_2==-3-D+E && meter_2>=1 ], cost: 12*meter_2 76: evalrank2bb3in -> evalrank2bb3in : D'=meter_3+D, E'=-4*meter_3+E, F'=free, G'=meter_3+D, H'=1-4*meter_3+E, Q'=free_1, J'=-4*meter_3+E, [ free>=1 && free_1>=1 && 3==-3-D+E && 5*meter_3==-5-D+E && meter_3>=1 ], cost: 14*meter_3 77: evalrank2bb3in -> evalrank2bb3in : E'=E-2*meter_4-2*meter_1*meter_4, F'=free, G'=D, H'=1+E-2*meter_4-2*meter_1*meter_4, Q'=free_1, J'=E-2*meter_4-2*meter_1*meter_4, [ free>=1 && -1+E>=3+D && 0>=free_1 && 2+D>=-3+E && 2*meter_1==-2-D+E && meter_1>=1 && 5*meter_4==-3-D-meter_1+E && meter_4>=1 ], cost: 12*meter_4+9*meter_1*meter_4 Chained accelerated rules (with incoming rules): Start location: evalrank2start 46: evalrank2start -> evalrank2bb1in : A'=B, C'=B, [], cost: 11 47: evalrank2bb1in -> evalrank2bb3in : D'=-1+A, E'=-1+C+A, [ A>=2 ], cost: 2 78: evalrank2bb1in -> evalrank2bb3in : D'=-1+A, E'=-1+C+A-2*meter_1, F'=free, G'=-1+A, H'=C+A-2*meter_1, J'=-1+C+A-2*meter_1, [ A>=2 && -1+C+A>=A && free>=1 && 1+A>=-2+C+A && 2*meter_1==C && meter_1>=1 ], cost: 2+9*meter_1 79: evalrank2bb1in -> evalrank2bb3in : D'=-1+A, E'=-1+C-2*meter_2+A, F'=free, G'=-1+A, H'=C-2*meter_2+A, Q'=free_1, J'=-1+C-2*meter_2+A, [ A>=2 && free>=1 && -2+C+A>=2+A && 0>=free_1 && 2*meter_2==-3+C && meter_2>=1 ], cost: 2+12*meter_2 62: evalrank2bb3in -> evalrank2bb1in : A'=-1+D, C'=1-D+E, K'=-1+D, L'=1-D+E, [ D>=E ], cost: 6 63: evalrank2bb3in -> evalrank2bb1in : A'=-1+D, C'=1-D+E, F'=free, K'=-1+D, L'=1-D+E, [ E>=1+D && 0>=free ], cost: 9 73: evalrank2bb3in -> [34] : [ free>=1 && -1+E>=3+D && free_1>=1 && 3*meter==-3-D+E && meter>=1 ], cost: 5+5*meter Eliminated locations (on tree-shaped paths): Start location: evalrank2start 46: evalrank2start -> evalrank2bb1in : A'=B, C'=B, [], cost: 11 80: evalrank2bb1in -> evalrank2bb1in : A'=-2+A, C'=1+C, D'=-1+A, E'=-1+C+A, K'=-2+A, L'=1+C, [ A>=2 && -1+A>=-1+C+A ], cost: 8 81: evalrank2bb1in -> evalrank2bb1in : A'=-2+A, C'=1+C, D'=-1+A, E'=-1+C+A, F'=free, K'=-2+A, L'=1+C, [ A>=2 && -1+C+A>=A && 0>=free ], cost: 11 82: evalrank2bb1in -> [34] : D'=-1+A, E'=-1+C+A, [ A>=2 && free>=1 && -2+C+A>=2+A && free_1>=1 && 3*meter==-3+C && meter>=1 ], cost: 7+5*meter 83: evalrank2bb1in -> evalrank2bb1in : A'=-2+A, C'=1+C-2*meter_1, D'=-1+A, E'=-1+C+A-2*meter_1, F'=free, G'=-1+A, H'=C+A-2*meter_1, J'=-1+C+A-2*meter_1, K'=-2+A, L'=1+C-2*meter_1, [ A>=2 && -1+C+A>=A && free>=1 && 1+A>=-2+C+A && 2*meter_1==C && meter_1>=1 ], cost: 8+9*meter_1 84: evalrank2bb1in -> [36] : [ A>=2 && -1+C+A>=A && free>=1 && 1+A>=-2+C+A && 2*meter_1==C && meter_1>=1 ], cost: 2+9*meter_1 85: evalrank2bb1in -> [36] : [ A>=2 && free>=1 && -2+C+A>=2+A && 0>=free_1 && 2*meter_2==-3+C && meter_2>=1 ], cost: 2+12*meter_2 Accelerating simple loops of location 11. Accelerating the following rules: 80: evalrank2bb1in -> evalrank2bb1in : A'=-2+A, C'=1+C, D'=-1+A, E'=-1+C+A, K'=-2+A, L'=1+C, [ A>=2 && -1+A>=-1+C+A ], cost: 8 81: evalrank2bb1in -> evalrank2bb1in : A'=-2+A, C'=1+C, D'=-1+A, E'=-1+C+A, F'=free, K'=-2+A, L'=1+C, [ A>=2 && -1+C+A>=A && 0>=free ], cost: 11 83: evalrank2bb1in -> evalrank2bb1in : A'=-2+A, C'=1+C-2*meter_1, D'=-1+A, E'=-1+C+A-2*meter_1, F'=free, G'=-1+A, H'=C+A-2*meter_1, J'=-1+C+A-2*meter_1, K'=-2+A, L'=1+C-2*meter_1, [ A>=2 && -1+C+A>=A && free>=1 && 1+A>=-2+C+A && 2*meter_1==C && meter_1>=1 ], cost: 8+9*meter_1 Found no metering function for rule 80. Accelerated rule 81 with metering function meter_6 (where 2*meter_6==-1+A), yielding the new rule 86. Accelerated rule 83 with metering function meter_7 (where 2*meter_7==C-2*meter_1), yielding the new rule 87. During metering: Instantiating temporary variables by {meter_6==1} Removing the simple loops: 81 83. Accelerated all simple loops using metering functions (where possible): Start location: evalrank2start 46: evalrank2start -> evalrank2bb1in : A'=B, C'=B, [], cost: 11 80: evalrank2bb1in -> evalrank2bb1in : A'=-2+A, C'=1+C, D'=-1+A, E'=-1+C+A, K'=-2+A, L'=1+C, [ A>=2 && -1+A>=-1+C+A ], cost: 8 82: evalrank2bb1in -> [34] : D'=-1+A, E'=-1+C+A, [ A>=2 && free>=1 && -2+C+A>=2+A && free_1>=1 && 3*meter==-3+C && meter>=1 ], cost: 7+5*meter 84: evalrank2bb1in -> [36] : [ A>=2 && -1+C+A>=A && free>=1 && 1+A>=-2+C+A && 2*meter_1==C && meter_1>=1 ], cost: 2+9*meter_1 85: evalrank2bb1in -> [36] : [ A>=2 && free>=1 && -2+C+A>=2+A && 0>=free_1 && 2*meter_2==-3+C && meter_2>=1 ], cost: 2+12*meter_2 86: evalrank2bb1in -> evalrank2bb1in : A'=-2*meter_6+A, C'=meter_6+C, D'=1-2*meter_6+A, E'=-meter_6+C+A, F'=free, K'=-2*meter_6+A, L'=meter_6+C, [ A>=2 && -1+C+A>=A && 0>=free && 2*meter_6==-1+A && meter_6>=1 ], cost: 11*meter_6 87: evalrank2bb1in -> evalrank2bb1in : A'=-2*meter_7+A, C'=C+meter_7-2*meter_7*meter_1, D'=1-2*meter_7+A, E'=C-meter_7+A-2*meter_7*meter_1, F'=free, G'=1-2*meter_7+A, H'=1+C-meter_7+A-2*meter_7*meter_1, J'=C-meter_7+A-2*meter_7*meter_1, K'=-2*meter_7+A, L'=C+meter_7-2*meter_7*meter_1, [ A>=2 && -1+C+A>=A && free>=1 && 1+A>=-2+C+A && 2*meter_1==C && meter_1>=1 && 2*meter_7==C-2*meter_1 && meter_7>=1 ], cost: 8*meter_7+9*meter_7*meter_1 Chained accelerated rules (with incoming rules): Start location: evalrank2start 46: evalrank2start -> evalrank2bb1in : A'=B, C'=B, [], cost: 11 88: evalrank2start -> evalrank2bb1in : A'=-2*meter_6+B, C'=meter_6+B, D'=1-2*meter_6+B, E'=-meter_6+2*B, F'=free, K'=-2*meter_6+B, L'=meter_6+B, [ B>=2 && 0>=free && 2*meter_6==-1+B && meter_6>=1 ], cost: 11+11*meter_6 82: evalrank2bb1in -> [34] : D'=-1+A, E'=-1+C+A, [ A>=2 && free>=1 && -2+C+A>=2+A && free_1>=1 && 3*meter==-3+C && meter>=1 ], cost: 7+5*meter 84: evalrank2bb1in -> [36] : [ A>=2 && -1+C+A>=A && free>=1 && 1+A>=-2+C+A && 2*meter_1==C && meter_1>=1 ], cost: 2+9*meter_1 85: evalrank2bb1in -> [36] : [ A>=2 && free>=1 && -2+C+A>=2+A && 0>=free_1 && 2*meter_2==-3+C && meter_2>=1 ], cost: 2+12*meter_2 Eliminated locations (on tree-shaped paths): Start location: evalrank2start 89: evalrank2start -> [34] : A'=B, C'=B, D'=-1+B, E'=-1+2*B, [ free>=1 && -2+2*B>=2+B && free_1>=1 && 3*meter==-3+B && meter>=1 ], cost: 18+5*meter 90: evalrank2start -> [36] : A'=B, C'=B, [ B>=2 && free>=1 && 1+B>=-2+2*B && 2*meter_1==B && meter_1>=1 ], cost: 13+9*meter_1 91: evalrank2start -> [36] : A'=B, C'=B, [ free>=1 && -2+2*B>=2+B && 0>=free_1 && 2*meter_2==-3+B && meter_2>=1 ], cost: 13+12*meter_2 92: evalrank2start -> [38] : [ B>=2 && 0>=free && 2*meter_6==-1+B && meter_6>=1 ], cost: 11+11*meter_6 ### Computing asymptotic complexity ### Fully simplified ITS problem Start location: evalrank2start 89: evalrank2start -> [34] : A'=B, C'=B, D'=-1+B, E'=-1+2*B, [ free>=1 && -2+2*B>=2+B && free_1>=1 && 3*meter==-3+B && meter>=1 ], cost: 18+5*meter 90: evalrank2start -> [36] : A'=B, C'=B, [ B>=2 && free>=1 && 1+B>=-2+2*B && 2*meter_1==B && meter_1>=1 ], cost: 13+9*meter_1 91: evalrank2start -> [36] : A'=B, C'=B, [ free>=1 && -2+2*B>=2+B && 0>=free_1 && 2*meter_2==-3+B && meter_2>=1 ], cost: 13+12*meter_2 92: evalrank2start -> [38] : [ B>=2 && 0>=free && 2*meter_6==-1+B && meter_6>=1 ], cost: 11+11*meter_6 Computing asymptotic complexity for rule 89 Solved the limit problem by the following transformations: Created initial limit problem: 18+5*meter (+), -2-3*meter+B (+/+!), 4+3*meter-B (+/+!), free (+/+!), -3+B (+/+!), free_1 (+/+!) [not solved] removing all constraints (solved by SMT) resulting limit problem: [solved] applying transformation rule (C) using substitution {free==n,meter==n,B==3+3*n,free_1==n} resulting limit problem: [solved] Solution: free / n meter / n B / 3+3*n free_1 / n Resulting cost 18+5*n has complexity: Poly(n^1) Found new complexity Poly(n^1). Computing asymptotic complexity for rule 90 Could not solve the limit problem. Resulting cost 0 has complexity: Unknown Computing asymptotic complexity for rule 91 Solved the limit problem by the following transformations: Created initial limit problem: -2-2*meter_2+B (+/+!), 1-free_1 (+/+!), free (+/+!), -3+B (+/+!), 13+12*meter_2 (+), 4+2*meter_2-B (+/+!) [not solved] applying transformation rule (C) using substitution {B==3+2*meter_2} resulting limit problem: 1 (+/+!), 2*meter_2 (+/+!), 1-free_1 (+/+!), free (+/+!), 13+12*meter_2 (+) [not solved] applying transformation rule (C) using substitution {free==1} resulting limit problem: 1 (+/+!), 2*meter_2 (+/+!), 1-free_1 (+/+!), 13+12*meter_2 (+) [not solved] applying transformation rule (C) using substitution {free_1==0} resulting limit problem: 1 (+/+!), 2*meter_2 (+/+!), 13+12*meter_2 (+) [not solved] applying transformation rule (B), deleting 1 (+/+!) resulting limit problem: 2*meter_2 (+/+!), 13+12*meter_2 (+) [not solved] removing all constraints (solved by SMT) resulting limit problem: [solved] applying transformation rule (C) using substitution {meter_2==n} resulting limit problem: [solved] Solved the limit problem by the following transformations: Created initial limit problem: -2-2*meter_2+B (+/+!), 1-free_1 (+/+!), free (+/+!), -3+B (+/+!), 13+12*meter_2 (+), 4+2*meter_2-B (+/+!) [not solved] applying transformation rule (C) using substitution {B==3+2*meter_2} resulting limit problem: 1 (+/+!), 2*meter_2 (+/+!), 1-free_1 (+/+!), free (+/+!), 13+12*meter_2 (+) [not solved] applying transformation rule (B), deleting 1 (+/+!) resulting limit problem: 2*meter_2 (+/+!), 1-free_1 (+/+!), free (+/+!), 13+12*meter_2 (+) [not solved] removing all constraints (solved by SMT) resulting limit problem: [solved] applying transformation rule (C) using substitution {meter_2==n,free==n,free_1==-n} resulting limit problem: [solved] Solved the limit problem by the following transformations: Created initial limit problem: -2-2*meter_2+B (+/+!), 1-free_1 (+/+!), free (+/+!), -3+B (+/+!), 13+12*meter_2 (+), 4+2*meter_2-B (+/+!) [not solved] applying transformation rule (C) using substitution {B==3+2*meter_2} resulting limit problem: 1 (+/+!), 2*meter_2 (+/+!), 1-free_1 (+/+!), free (+/+!), 13+12*meter_2 (+) [not solved] applying transformation rule (C) using substitution {free_1==0} resulting limit problem: 1 (+/+!), 2*meter_2 (+/+!), free (+/+!), 13+12*meter_2 (+) [not solved] applying transformation rule (B), deleting 1 (+/+!) resulting limit problem: 2*meter_2 (+/+!), free (+/+!), 13+12*meter_2 (+) [not solved] removing all constraints (solved by SMT) resulting limit problem: [solved] applying transformation rule (C) using substitution {meter_2==n,free==1} resulting limit problem: [solved] Solved the limit problem by the following transformations: Created initial limit problem: -2-2*meter_2+B (+/+!), 1-free_1 (+/+!), free (+/+!), -3+B (+/+!), 13+12*meter_2 (+), 4+2*meter_2-B (+/+!) [not solved] applying transformation rule (C) using substitution {B==3+2*meter_2} resulting limit problem: 1 (+/+!), 2*meter_2 (+/+!), 1-free_1 (+/+!), free (+/+!), 13+12*meter_2 (+) [not solved] applying transformation rule (C) using substitution {free==1} resulting limit problem: 1 (+/+!), 2*meter_2 (+/+!), 1-free_1 (+/+!), 13+12*meter_2 (+) [not solved] applying transformation rule (B), deleting 1 (+/+!) resulting limit problem: 2*meter_2 (+/+!), 1-free_1 (+/+!), 13+12*meter_2 (+) [not solved] removing all constraints (solved by SMT) resulting limit problem: [solved] applying transformation rule (C) using substitution {meter_2==n,free_1==0} resulting limit problem: [solved] Solution: meter_2 / n free / 1 B / 3+2*n free_1 / 0 Resulting cost 13+12*n has complexity: Poly(n^1) Computing asymptotic complexity for rule 92 Solved the limit problem by the following transformations: Created initial limit problem: 11+11*meter_6 (+), -1+B (+/+!), 2+2*meter_6-B (+/+!), -2*meter_6+B (+/+!), 1-free (+/+!) [not solved] applying transformation rule (C) using substitution {B==1+2*meter_6} resulting limit problem: 1 (+/+!), 11+11*meter_6 (+), 2*meter_6 (+/+!), 1-free (+/+!) [not solved] applying transformation rule (C) using substitution {free==0} resulting limit problem: 1 (+/+!), 11+11*meter_6 (+), 2*meter_6 (+/+!) [not solved] applying transformation rule (B), deleting 1 (+/+!) resulting limit problem: 11+11*meter_6 (+), 2*meter_6 (+/+!) [not solved] removing all constraints (solved by SMT) resulting limit problem: [solved] applying transformation rule (C) using substitution {meter_6==n} resulting limit problem: [solved] Solved the limit problem by the following transformations: Created initial limit problem: 11+11*meter_6 (+), -1+B (+/+!), 2+2*meter_6-B (+/+!), -2*meter_6+B (+/+!), 1-free (+/+!) [not solved] applying transformation rule (C) using substitution {B==1+2*meter_6} resulting limit problem: 1 (+/+!), 11+11*meter_6 (+), 2*meter_6 (+/+!), 1-free (+/+!) [not solved] applying transformation rule (B), deleting 1 (+/+!) resulting limit problem: 11+11*meter_6 (+), 2*meter_6 (+/+!), 1-free (+/+!) [not solved] removing all constraints (solved by SMT) resulting limit problem: [solved] applying transformation rule (C) using substitution {meter_6==n,free==-n} resulting limit problem: [solved] Solution: meter_6 / n free / 0 B / 1+2*n Resulting cost 11+11*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: 18+5*n Rule cost: 18+5*meter Rule guard: [ free>=1 && -2+2*B>=2+B && free_1>=1 && 3*meter==-3+B ] WORST_CASE(Omega(n^1),?) ---------------------------------------- (2) BOUNDS(n^1, INF)