WORST_CASE(INF,?) ### Pre-processing the ITS problem ### Initial linear ITS problem Start location: __init 0: f1_0_main_New -> f536_0_copy_InvokeMethod : arg1'=arg1P_1, arg2'=arg2P_1, [ arg2P_1>0 && arg1P_1>4 ], cost: 1 1: f536_0_copy_InvokeMethod -> f536_0_copy_InvokeMethod : arg1'=arg1P_2, arg2'=arg2P_2, [ 2+arg1P_2<=arg1 && 3+arg2P_2<=arg1 && arg1>2 && arg2>0 && arg1P_2>0 && arg2P_2>-1 ], cost: 1 2: f536_0_copy_InvokeMethod -> f536_0_copy_InvokeMethod : arg1'=arg1P_3, arg2'=arg2P_3, [ 2+arg1P_3<=arg1 && 3+arg2P_3<=arg1 && arg1>2 && arg2>0 && arg1P_3>0 && arg2P_3>-1 ], cost: 1 3: f536_0_copy_InvokeMethod -> f536_0_copy_InvokeMethod : arg1'=arg1P_4, arg2'=arg2P_4, [ 2+arg1P_4<=arg1 && 3+arg2P_4<=arg1 && arg1>2 && arg2>0 && arg1P_4>0 && arg2P_4>-1 ], cost: 1 4: __init -> f1_0_main_New : arg1'=arg1P_5, arg2'=arg2P_5, [], cost: 1 Checking for constant complexity: The following rule is satisfiable with cost >= 1, yielding constant complexity: 4: __init -> f1_0_main_New : arg1'=arg1P_5, arg2'=arg2P_5, [], cost: 1 ### Simplification by acceleration and chaining ### Accelerating simple loops of location 1. Accelerating the following rules: 1: f536_0_copy_InvokeMethod -> f536_0_copy_InvokeMethod : arg1'=arg1P_2, arg2'=arg2P_2, [ 2+arg1P_2<=arg1 && 3+arg2P_2<=arg1 && arg1>2 && arg2>0 && arg1P_2>0 && arg2P_2>-1 ], cost: 1 2: f536_0_copy_InvokeMethod -> f536_0_copy_InvokeMethod : arg1'=arg1P_3, arg2'=arg2P_3, [ 2+arg1P_3<=arg1 && 3+arg2P_3<=arg1 && arg1>2 && arg2>0 && arg1P_3>0 && arg2P_3>-1 ], cost: 1 3: f536_0_copy_InvokeMethod -> f536_0_copy_InvokeMethod : arg1'=arg1P_4, arg2'=arg2P_4, [ 2+arg1P_4<=arg1 && 3+arg2P_4<=arg1 && arg1>2 && arg2>0 && arg1P_4>0 && arg2P_4>-1 ], cost: 1 During metering: Instantiating temporary variables by {arg1P_2==-2+arg1,arg2P_2==-3+arg1P_2} Accelerated rule 1 with metering function meter (where 2*meter==-1-arg1P_2+arg1) (after strengthening guard), yielding the new rule 5. During metering: Instantiating temporary variables by {arg2P_3==-3+arg1P_3,arg1P_3==-2+arg1} Accelerated rule 2 with metering function meter_1 (where 2*meter_1==-1+arg1-arg1P_3) (after strengthening guard), yielding the new rule 6. During metering: Instantiating temporary variables by {arg1P_4==-2+arg1,arg2P_4==-3+arg1P_4} Accelerated rule 3 with metering function meter_2 (where 2*meter_2==-1+arg1-arg1P_4) (after strengthening guard), yielding the new rule 7. During metering: Instantiating temporary variables by {meter==1,arg1P_3==-2+arg1} During metering: Instantiating temporary variables by {arg1P_4==-2+arg1,meter==1} During metering: Instantiating temporary variables by {meter_1==1,arg1P_3==4-2*meter_1} During metering: Instantiating temporary variables by {meter_1==1,arg1P_3==4-2*meter_1} During metering: Instantiating temporary variables by {meter_2==1,arg1P_4==4-2*meter_2} During metering: Instantiating temporary variables by {meter_2==1,arg1P_3==-2+arg1} Removing the simple loops:. Accelerated all simple loops using metering functions (where possible): Start location: __init 0: f1_0_main_New -> f536_0_copy_InvokeMethod : arg1'=arg1P_1, arg2'=arg2P_1, [ arg2P_1>0 && arg1P_1>4 ], cost: 1 1: f536_0_copy_InvokeMethod -> f536_0_copy_InvokeMethod : arg1'=arg1P_2, arg2'=arg2P_2, [ 2+arg1P_2<=arg1 && 3+arg2P_2<=arg1 && arg1>2 && arg2>0 && arg1P_2>0 && arg2P_2>-1 ], cost: 1 2: f536_0_copy_InvokeMethod -> f536_0_copy_InvokeMethod : arg1'=arg1P_3, arg2'=arg2P_3, [ 2+arg1P_3<=arg1 && 3+arg2P_3<=arg1 && arg1>2 && arg2>0 && arg1P_3>0 && arg2P_3>-1 ], cost: 1 3: f536_0_copy_InvokeMethod -> f536_0_copy_InvokeMethod : arg1'=arg1P_4, arg2'=arg2P_4, [ 2+arg1P_4<=arg1 && 3+arg2P_4<=arg1 && arg1>2 && arg2>0 && arg1P_4>0 && arg2P_4>-1 ], cost: 1 5: f536_0_copy_InvokeMethod -> f536_0_copy_InvokeMethod : arg1'=arg1-2*meter, arg2'=-3+arg1P_2, [ arg2>0 && arg1P_2<=-2+arg1 && -2+arg1>2 && -3+arg1P_2>0 && 2*meter==-1-arg1P_2+arg1 && meter>=1 ], cost: meter 6: f536_0_copy_InvokeMethod -> f536_0_copy_InvokeMethod : arg1'=arg1-2*meter_1, arg2'=-3+arg1P_3, [ arg2>0 && arg1P_3<=-2+arg1 && -2+arg1>2 && -3+arg1P_3>0 && 2*meter_1==-1+arg1-arg1P_3 && meter_1>=1 ], cost: meter_1 7: f536_0_copy_InvokeMethod -> f536_0_copy_InvokeMethod : arg1'=-2*meter_2+arg1, arg2'=-3+arg1P_4, [ arg2>0 && arg1P_4<=-2+arg1 && -2+arg1>2 && -3+arg1P_4>0 && 2*meter_2==-1+arg1-arg1P_4 && meter_2>=1 ], cost: meter_2 4: __init -> f1_0_main_New : arg1'=arg1P_5, arg2'=arg2P_5, [], cost: 1 Chained accelerated rules (with incoming rules): Start location: __init 0: f1_0_main_New -> f536_0_copy_InvokeMethod : arg1'=arg1P_1, arg2'=arg2P_1, [ arg2P_1>0 && arg1P_1>4 ], cost: 1 8: f1_0_main_New -> f536_0_copy_InvokeMethod : arg1'=arg1P_2, arg2'=arg2P_2, [ arg1P_2>0 && arg2P_2>-1 ], cost: 2 9: f1_0_main_New -> f536_0_copy_InvokeMethod : arg1'=arg1P_3, arg2'=arg2P_3, [ arg1P_3>0 && arg2P_3>-1 ], cost: 2 10: f1_0_main_New -> f536_0_copy_InvokeMethod : arg1'=arg1P_4, arg2'=arg2P_4, [ arg1P_4>0 && arg2P_4>-1 ], cost: 2 11: f1_0_main_New -> f536_0_copy_InvokeMethod : arg1'=arg1P_1-2*meter, arg2'=-4+arg1P_1-2*meter, [ arg1P_1>4 && -1+arg1P_1-2*meter<=-2+arg1P_1 && -4+arg1P_1-2*meter>0 && meter>=1 ], cost: 1+meter 12: f1_0_main_New -> f536_0_copy_InvokeMethod : arg1'=1+arg1P_3, arg2'=-3+arg1P_3, [ 1+2*meter_1+arg1P_3>4 && arg1P_3<=-1+2*meter_1+arg1P_3 && -3+arg1P_3>0 && meter_1>=1 ], cost: 1+meter_1 13: f1_0_main_New -> f536_0_copy_InvokeMethod : arg1'=-2*meter_2+arg1P_1, arg2'=-4-2*meter_2+arg1P_1, [ arg1P_1>4 && -1-2*meter_2+arg1P_1<=-2+arg1P_1 && -4-2*meter_2+arg1P_1>0 && meter_2>=1 ], cost: 1+meter_2 4: __init -> f1_0_main_New : arg1'=arg1P_5, arg2'=arg2P_5, [], cost: 1 Removed unreachable locations (and leaf rules with constant cost): Start location: __init 11: f1_0_main_New -> f536_0_copy_InvokeMethod : arg1'=arg1P_1-2*meter, arg2'=-4+arg1P_1-2*meter, [ arg1P_1>4 && -1+arg1P_1-2*meter<=-2+arg1P_1 && -4+arg1P_1-2*meter>0 && meter>=1 ], cost: 1+meter 12: f1_0_main_New -> f536_0_copy_InvokeMethod : arg1'=1+arg1P_3, arg2'=-3+arg1P_3, [ 1+2*meter_1+arg1P_3>4 && arg1P_3<=-1+2*meter_1+arg1P_3 && -3+arg1P_3>0 && meter_1>=1 ], cost: 1+meter_1 13: f1_0_main_New -> f536_0_copy_InvokeMethod : arg1'=-2*meter_2+arg1P_1, arg2'=-4-2*meter_2+arg1P_1, [ arg1P_1>4 && -1-2*meter_2+arg1P_1<=-2+arg1P_1 && -4-2*meter_2+arg1P_1>0 && meter_2>=1 ], cost: 1+meter_2 4: __init -> f1_0_main_New : arg1'=arg1P_5, arg2'=arg2P_5, [], cost: 1 Eliminated locations (on tree-shaped paths): Start location: __init 14: __init -> f536_0_copy_InvokeMethod : arg1'=arg1P_1-2*meter, arg2'=-4+arg1P_1-2*meter, [ arg1P_1>4 && -1+arg1P_1-2*meter<=-2+arg1P_1 && -4+arg1P_1-2*meter>0 && meter>=1 ], cost: 2+meter 15: __init -> f536_0_copy_InvokeMethod : arg1'=1+arg1P_3, arg2'=-3+arg1P_3, [ 1+2*meter_1+arg1P_3>4 && arg1P_3<=-1+2*meter_1+arg1P_3 && -3+arg1P_3>0 && meter_1>=1 ], cost: 2+meter_1 16: __init -> f536_0_copy_InvokeMethod : arg1'=-2*meter_2+arg1P_1, arg2'=-4-2*meter_2+arg1P_1, [ arg1P_1>4 && -1-2*meter_2+arg1P_1<=-2+arg1P_1 && -4-2*meter_2+arg1P_1>0 && meter_2>=1 ], cost: 2+meter_2 ### Computing asymptotic complexity ### Fully simplified ITS problem Start location: __init 14: __init -> f536_0_copy_InvokeMethod : arg1'=arg1P_1-2*meter, arg2'=-4+arg1P_1-2*meter, [ arg1P_1>4 && -1+arg1P_1-2*meter<=-2+arg1P_1 && -4+arg1P_1-2*meter>0 && meter>=1 ], cost: 2+meter 15: __init -> f536_0_copy_InvokeMethod : arg1'=1+arg1P_3, arg2'=-3+arg1P_3, [ 1+2*meter_1+arg1P_3>4 && arg1P_3<=-1+2*meter_1+arg1P_3 && -3+arg1P_3>0 && meter_1>=1 ], cost: 2+meter_1 16: __init -> f536_0_copy_InvokeMethod : arg1'=-2*meter_2+arg1P_1, arg2'=-4-2*meter_2+arg1P_1, [ arg1P_1>4 && -1-2*meter_2+arg1P_1<=-2+arg1P_1 && -4-2*meter_2+arg1P_1>0 && meter_2>=1 ], cost: 2+meter_2 Computing asymptotic complexity for rule 14 Simplified the guard: 14: __init -> f536_0_copy_InvokeMethod : arg1'=arg1P_1-2*meter, arg2'=-4+arg1P_1-2*meter, [ -1+arg1P_1-2*meter<=-2+arg1P_1 && -4+arg1P_1-2*meter>0 ], cost: 2+meter Solved the limit problem by the following transformations: Created initial limit problem: 2*meter (+/+!), -4+arg1P_1-2*meter (+/+!), 2+meter (+) [not solved] removing all constraints (solved by SMT) resulting limit problem: [solved] applying transformation rule (C) using substitution {arg1P_1==2*n,meter==-3+n} resulting limit problem: [solved] Solution: arg1P_1 / 2*n meter / -3+n Resulting cost -1+n has complexity: Unbounded Found new complexity Unbounded. Obtained the following overall complexity (w.r.t. the length of the input n): Complexity: Unbounded Cpx degree: Unbounded Solved cost: -1+n Rule cost: 2+meter Rule guard: [ -1+arg1P_1-2*meter<=-2+arg1P_1 && -4+arg1P_1-2*meter>0 ] WORST_CASE(INF,?)