WORST_CASE(Omega(1),?) ### Pre-processing the ITS problem ### Initial linear ITS problem Start location: __init 0: f1_0_main_Load -> f31_0_fib_NE : arg1'=arg1P_1, arg2'=arg2P_1, [ arg1>0 && arg2>-1 && arg2==arg1P_1 ], cost: 1 1: f31_0_fib_NE -> f31_0_fib_NE : arg1'=arg1P_2, arg2'=arg2P_2, [ arg1>1 && -1+arg1 f142_0_fib_InvokeMethod : arg1'=arg1P_3, arg2'=arg2P_3, [ 2==arg1 && 2==arg1P_3 && 0==arg2P_3 ], cost: 1 3: f31_0_fib_NE -> f142_0_fib_InvokeMethod : arg1'=arg1P_4, arg2'=arg2P_4, [ arg1>1 && -1+arg1 f31_0_fib_NE : arg1'=arg1P_6, arg2'=arg2P_6, [ arg1>1 && arg2 f142_0_fib_InvokeMethod : arg1'=arg1P_5, arg2'=arg2P_5, [ arg1>0 && arg1==arg1P_5 && -2+arg1==arg2P_5 ], cost: 1 6: __init -> f1_0_main_Load : arg1'=arg1P_7, arg2'=arg2P_7, [], cost: 1 Checking for constant complexity: The following rule is satisfiable with cost >= 1, yielding constant complexity: 6: __init -> f1_0_main_Load : arg1'=arg1P_7, arg2'=arg2P_7, [], cost: 1 Removed unreachable and leaf rules: Start location: __init 0: f1_0_main_Load -> f31_0_fib_NE : arg1'=arg1P_1, arg2'=arg2P_1, [ arg1>0 && arg2>-1 && arg2==arg1P_1 ], cost: 1 1: f31_0_fib_NE -> f31_0_fib_NE : arg1'=arg1P_2, arg2'=arg2P_2, [ arg1>1 && -1+arg1 f142_0_fib_InvokeMethod : arg1'=arg1P_3, arg2'=arg2P_3, [ 2==arg1 && 2==arg1P_3 && 0==arg2P_3 ], cost: 1 3: f31_0_fib_NE -> f142_0_fib_InvokeMethod : arg1'=arg1P_4, arg2'=arg2P_4, [ arg1>1 && -1+arg1 f31_0_fib_NE : arg1'=arg1P_6, arg2'=arg2P_6, [ arg1>1 && arg2 f1_0_main_Load : arg1'=arg1P_7, arg2'=arg2P_7, [], cost: 1 Simplified all rules, resulting in: Start location: __init 0: f1_0_main_Load -> f31_0_fib_NE : arg1'=arg2, arg2'=arg2P_1, [ arg1>0 && arg2>-1 ], cost: 1 1: f31_0_fib_NE -> f31_0_fib_NE : arg1'=-1+arg1, arg2'=arg2P_2, [ arg1>1 ], cost: 1 2: f31_0_fib_NE -> f142_0_fib_InvokeMethod : arg1'=2, arg2'=0, [ 2==arg1 ], cost: 1 3: f31_0_fib_NE -> f142_0_fib_InvokeMethod : arg2'=-2+arg1, [ arg1>1 ], cost: 1 5: f142_0_fib_InvokeMethod -> f31_0_fib_NE : arg1'=arg2, arg2'=arg2P_6, [ arg1>1 && arg2 f1_0_main_Load : arg1'=arg1P_7, arg2'=arg2P_7, [], cost: 1 ### Simplification by acceleration and chaining ### Accelerating simple loops of location 1. Accelerating the following rules: 1: f31_0_fib_NE -> f31_0_fib_NE : arg1'=-1+arg1, arg2'=arg2P_2, [ arg1>1 ], cost: 1 Accelerated rule 1 with backward acceleration, yielding the new rule 7. [accelerate] Nesting with 1 inner and 1 outer candidates Removing the simple loops: 1. Accelerated all simple loops using metering functions (where possible): Start location: __init 0: f1_0_main_Load -> f31_0_fib_NE : arg1'=arg2, arg2'=arg2P_1, [ arg1>0 && arg2>-1 ], cost: 1 2: f31_0_fib_NE -> f142_0_fib_InvokeMethod : arg1'=2, arg2'=0, [ 2==arg1 ], cost: 1 3: f31_0_fib_NE -> f142_0_fib_InvokeMethod : arg2'=-2+arg1, [ arg1>1 ], cost: 1 7: f31_0_fib_NE -> f31_0_fib_NE : arg1'=1, arg2'=arg2P_2, [ -1+arg1>=1 ], cost: -1+arg1 5: f142_0_fib_InvokeMethod -> f31_0_fib_NE : arg1'=arg2, arg2'=arg2P_6, [ arg1>1 && arg2 f1_0_main_Load : arg1'=arg1P_7, arg2'=arg2P_7, [], cost: 1 Chained accelerated rules (with incoming rules): Start location: __init 0: f1_0_main_Load -> f31_0_fib_NE : arg1'=arg2, arg2'=arg2P_1, [ arg1>0 && arg2>-1 ], cost: 1 8: f1_0_main_Load -> f31_0_fib_NE : arg1'=1, arg2'=arg2P_2, [ arg1>0 && -1+arg2>=1 ], cost: arg2 2: f31_0_fib_NE -> f142_0_fib_InvokeMethod : arg1'=2, arg2'=0, [ 2==arg1 ], cost: 1 3: f31_0_fib_NE -> f142_0_fib_InvokeMethod : arg2'=-2+arg1, [ arg1>1 ], cost: 1 5: f142_0_fib_InvokeMethod -> f31_0_fib_NE : arg1'=arg2, arg2'=arg2P_6, [ arg1>1 && arg2 f31_0_fib_NE : arg1'=1, arg2'=arg2P_2, [ arg1>1 && arg2=1 ], cost: arg2 6: __init -> f1_0_main_Load : arg1'=arg1P_7, arg2'=arg2P_7, [], cost: 1 Eliminated locations (on tree-shaped paths): Start location: __init 12: f31_0_fib_NE -> f31_0_fib_NE : arg1'=0, arg2'=arg2P_6, [ 2==arg1 ], cost: 2 13: f31_0_fib_NE -> f31_0_fib_NE : arg1'=-2+arg1, arg2'=arg2P_6, [ arg1>1 ], cost: 2 14: f31_0_fib_NE -> f31_0_fib_NE : arg1'=1, arg2'=arg2P_2, [ -3+arg1>=1 ], cost: -1+arg1 10: __init -> f31_0_fib_NE : arg1'=arg2P_7, arg2'=arg2P_1, [ arg1P_7>0 && arg2P_7>-1 ], cost: 2 11: __init -> f31_0_fib_NE : arg1'=1, arg2'=arg2P_2, [ arg1P_7>0 && -1+arg2P_7>=1 ], cost: 1+arg2P_7 Accelerating simple loops of location 1. Accelerating the following rules: 12: f31_0_fib_NE -> f31_0_fib_NE : arg1'=0, arg2'=arg2P_6, [ 2==arg1 ], cost: 2 13: f31_0_fib_NE -> f31_0_fib_NE : arg1'=-2+arg1, arg2'=arg2P_6, [ arg1>1 ], cost: 2 14: f31_0_fib_NE -> f31_0_fib_NE : arg1'=1, arg2'=arg2P_2, [ -3+arg1>=1 ], cost: -1+arg1 Failed to prove monotonicity of the guard of rule 12. Accelerated rule 13 with backward acceleration, yielding the new rule 15. Failed to prove monotonicity of the guard of rule 14. [accelerate] Nesting with 3 inner and 3 outer candidates Removing the simple loops: 13. Accelerated all simple loops using metering functions (where possible): Start location: __init 12: f31_0_fib_NE -> f31_0_fib_NE : arg1'=0, arg2'=arg2P_6, [ 2==arg1 ], cost: 2 14: f31_0_fib_NE -> f31_0_fib_NE : arg1'=1, arg2'=arg2P_2, [ -3+arg1>=1 ], cost: -1+arg1 15: f31_0_fib_NE -> f31_0_fib_NE : arg1'=-2*k_2+arg1, arg2'=arg2P_6, [ k_2>=1 && 2-2*k_2+arg1>1 ], cost: 2*k_2 10: __init -> f31_0_fib_NE : arg1'=arg2P_7, arg2'=arg2P_1, [ arg1P_7>0 && arg2P_7>-1 ], cost: 2 11: __init -> f31_0_fib_NE : arg1'=1, arg2'=arg2P_2, [ arg1P_7>0 && -1+arg2P_7>=1 ], cost: 1+arg2P_7 Chained accelerated rules (with incoming rules): Start location: __init 10: __init -> f31_0_fib_NE : arg1'=arg2P_7, arg2'=arg2P_1, [ arg1P_7>0 && arg2P_7>-1 ], cost: 2 11: __init -> f31_0_fib_NE : arg1'=1, arg2'=arg2P_2, [ arg1P_7>0 && -1+arg2P_7>=1 ], cost: 1+arg2P_7 16: __init -> f31_0_fib_NE : arg1'=0, arg2'=arg2P_6, [], cost: 4 17: __init -> f31_0_fib_NE : arg1'=1, arg2'=arg2P_2, [ -3+arg2P_7>=1 ], cost: 1+arg2P_7 18: __init -> f31_0_fib_NE : arg1'=arg2P_7-2*k_2, arg2'=arg2P_6, [ arg2P_7>-1 && k_2>=1 && 2+arg2P_7-2*k_2>1 ], cost: 2+2*k_2 Removed unreachable locations (and leaf rules with constant cost): Start location: __init 11: __init -> f31_0_fib_NE : arg1'=1, arg2'=arg2P_2, [ arg1P_7>0 && -1+arg2P_7>=1 ], cost: 1+arg2P_7 17: __init -> f31_0_fib_NE : arg1'=1, arg2'=arg2P_2, [ -3+arg2P_7>=1 ], cost: 1+arg2P_7 18: __init -> f31_0_fib_NE : arg1'=arg2P_7-2*k_2, arg2'=arg2P_6, [ arg2P_7>-1 && k_2>=1 && 2+arg2P_7-2*k_2>1 ], cost: 2+2*k_2 ### Computing asymptotic complexity ### Fully simplified ITS problem Start location: __init 11: __init -> f31_0_fib_NE : arg1'=1, arg2'=arg2P_2, [ arg1P_7>0 && -1+arg2P_7>=1 ], cost: 1+arg2P_7 17: __init -> f31_0_fib_NE : arg1'=1, arg2'=arg2P_2, [ -3+arg2P_7>=1 ], cost: 1+arg2P_7 18: __init -> f31_0_fib_NE : arg1'=arg2P_7-2*k_2, arg2'=arg2P_6, [ arg2P_7>-1 && k_2>=1 && 2+arg2P_7-2*k_2>1 ], cost: 2+2*k_2 Computing asymptotic complexity for rule 17 Resulting cost 0 has complexity: Unknown Computing asymptotic complexity for rule 11 Resulting cost 0 has complexity: Unknown Computing asymptotic complexity for rule 18 Simplified the guard: 18: __init -> f31_0_fib_NE : arg1'=arg2P_7-2*k_2, arg2'=arg2P_6, [ k_2>=1 && 2+arg2P_7-2*k_2>1 ], cost: 2+2*k_2 Resulting cost 0 has complexity: Unknown Obtained the following overall complexity (w.r.t. the length of the input n): Complexity: Constant Cpx degree: 0 Solved cost: 1 Rule cost: 1 Rule guard: [] WORST_CASE(Omega(1),?)