WORST_CASE(Omega(1),?)

### Pre-processing the ITS problem ###

Initial linear ITS problem
   Start location: __init
      0: f1 -> f2 : arg1'=arg1P_1, arg2'=arg2P_1, arg3'=arg3P_1, arg4'=arg4P_1, [ arg2==arg2P_1 && arg3==arg3P_1 && arg4==arg4P_1 ], cost: 1
      1: f2 -> f3 : arg1'=arg1P_2, arg2'=arg2P_2, arg3'=arg3P_2, arg4'=arg4P_2, [ arg1==arg1P_2 && arg3==arg3P_2 && arg4==arg4P_2 ], cost: 1
      2: f3 -> f4 : arg1'=arg1P_3, arg2'=arg2P_3, arg3'=arg3P_3, arg4'=arg4P_3, [ arg1==arg1P_3 && arg2==arg2P_3 && arg4==arg4P_3 ], cost: 1
      3: f4 -> f5 : arg1'=arg1P_4, arg2'=arg2P_4, arg3'=arg3P_4, arg4'=arg4P_4, [ arg1==arg1P_4 && arg2==arg2P_4 && arg3==arg3P_4 ], cost: 1
     14: f5 -> f6 : arg1'=arg1P_15, arg2'=arg2P_15, arg3'=arg3P_15, arg4'=arg4P_15, [ arg1>=1 && arg1==arg1P_15 && arg2==arg2P_15 && arg3==arg3P_15 && arg4==arg4P_15 ], cost: 1
     15: f5 -> f7 : arg1'=arg1P_16, arg2'=arg2P_16, arg3'=arg3P_16, arg4'=arg4P_16, [ arg1<1 && arg1==arg1P_16 && arg2==arg2P_16 && arg3==arg3P_16 && arg4==arg4P_16 ], cost: 1
      4: f6 -> f9 : arg1'=arg1P_5, arg2'=arg2P_5, arg3'=arg3P_5, arg4'=arg4P_5, [ arg1==arg1P_5 && 0==arg2P_5 && arg3==arg3P_5 && arg4==arg4P_5 ], cost: 1
     11: f9 -> f10 : arg1'=arg1P_12, arg2'=arg2P_12, arg3'=arg3P_12, arg4'=arg4P_12, [ arg2<arg4 && arg1==arg1P_12 && arg2==arg2P_12 && arg3==arg3P_12 && arg4==arg4P_12 ], cost: 1
     13: f9 -> f16 : arg1'=arg1P_14, arg2'=arg2P_14, arg3'=arg3P_14, arg4'=arg4P_14, [ arg2>=arg4 && arg1==arg1P_14 && arg2==arg2P_14 && arg3==arg3P_14 && arg4==arg4P_14 ], cost: 1
      5: f10 -> f11 : arg1'=arg1P_6, arg2'=arg2P_6, arg3'=arg3P_6, arg4'=arg4P_6, [ arg1==arg1P_6 && arg2==arg2P_6 && 0==arg3P_6 && arg4==arg4P_6 ], cost: 1
      7: f11 -> f12 : arg1'=arg1P_8, arg2'=arg2P_8, arg3'=arg3P_8, arg4'=arg4P_8, [ arg3<=arg2 && arg1==arg1P_8 && arg2==arg2P_8 && arg3==arg3P_8 && arg4==arg4P_8 ], cost: 1
      9: f11 -> f14 : arg1'=arg1P_10, arg2'=arg2P_10, arg3'=arg3P_10, arg4'=arg4P_10, [ arg3>arg2 && arg1==arg1P_10 && arg2==arg2P_10 && arg3==arg3P_10 && arg4==arg4P_10 ], cost: 1
      6: f12 -> f13 : arg1'=arg1P_7, arg2'=arg2P_7, arg3'=arg3P_7, arg4'=arg4P_7, [ arg3P_7==arg3+arg1 && arg1==arg1P_7 && arg2==arg2P_7 && arg4==arg4P_7 ], cost: 1
      8: f13 -> f11 : arg1'=arg1P_9, arg2'=arg2P_9, arg3'=arg3P_9, arg4'=arg4P_9, [ arg1==arg1P_9 && arg2==arg2P_9 && arg3==arg3P_9 && arg4==arg4P_9 ], cost: 1
     10: f14 -> f15 : arg1'=arg1P_11, arg2'=arg2P_11, arg3'=arg3P_11, arg4'=arg4P_11, [ arg2P_11==1+arg2 && arg1==arg1P_11 && arg3==arg3P_11 && arg4==arg4P_11 ], cost: 1
     12: f15 -> f9 : arg1'=arg1P_13, arg2'=arg2P_13, arg3'=arg3P_13, arg4'=arg4P_13, [ arg1==arg1P_13 && arg2==arg2P_13 && arg3==arg3P_13 && arg4==arg4P_13 ], cost: 1
     16: f16 -> f8 : arg1'=arg1P_17, arg2'=arg2P_17, arg3'=arg3P_17, arg4'=arg4P_17, [ arg1==arg1P_17 && arg2==arg2P_17 && arg3==arg3P_17 && arg4==arg4P_17 ], cost: 1
     17: f7 -> f8 : arg1'=arg1P_18, arg2'=arg2P_18, arg3'=arg3P_18, arg4'=arg4P_18, [ arg1==arg1P_18 && arg2==arg2P_18 && arg3==arg3P_18 && arg4==arg4P_18 ], cost: 1
     18: __init -> f1 : arg1'=arg1P_19, arg2'=arg2P_19, arg3'=arg3P_19, arg4'=arg4P_19, [], cost: 1

Checking for constant complexity:
   The following rule is satisfiable with cost >= 1, yielding constant complexity:
     18: __init -> f1 : arg1'=arg1P_19, arg2'=arg2P_19, arg3'=arg3P_19, arg4'=arg4P_19, [], cost: 1

Removed unreachable and leaf rules:
   Start location: __init
      0: f1 -> f2 : arg1'=arg1P_1, arg2'=arg2P_1, arg3'=arg3P_1, arg4'=arg4P_1, [ arg2==arg2P_1 && arg3==arg3P_1 && arg4==arg4P_1 ], cost: 1
      1: f2 -> f3 : arg1'=arg1P_2, arg2'=arg2P_2, arg3'=arg3P_2, arg4'=arg4P_2, [ arg1==arg1P_2 && arg3==arg3P_2 && arg4==arg4P_2 ], cost: 1
      2: f3 -> f4 : arg1'=arg1P_3, arg2'=arg2P_3, arg3'=arg3P_3, arg4'=arg4P_3, [ arg1==arg1P_3 && arg2==arg2P_3 && arg4==arg4P_3 ], cost: 1
      3: f4 -> f5 : arg1'=arg1P_4, arg2'=arg2P_4, arg3'=arg3P_4, arg4'=arg4P_4, [ arg1==arg1P_4 && arg2==arg2P_4 && arg3==arg3P_4 ], cost: 1
     14: f5 -> f6 : arg1'=arg1P_15, arg2'=arg2P_15, arg3'=arg3P_15, arg4'=arg4P_15, [ arg1>=1 && arg1==arg1P_15 && arg2==arg2P_15 && arg3==arg3P_15 && arg4==arg4P_15 ], cost: 1
      4: f6 -> f9 : arg1'=arg1P_5, arg2'=arg2P_5, arg3'=arg3P_5, arg4'=arg4P_5, [ arg1==arg1P_5 && 0==arg2P_5 && arg3==arg3P_5 && arg4==arg4P_5 ], cost: 1
     11: f9 -> f10 : arg1'=arg1P_12, arg2'=arg2P_12, arg3'=arg3P_12, arg4'=arg4P_12, [ arg2<arg4 && arg1==arg1P_12 && arg2==arg2P_12 && arg3==arg3P_12 && arg4==arg4P_12 ], cost: 1
      5: f10 -> f11 : arg1'=arg1P_6, arg2'=arg2P_6, arg3'=arg3P_6, arg4'=arg4P_6, [ arg1==arg1P_6 && arg2==arg2P_6 && 0==arg3P_6 && arg4==arg4P_6 ], cost: 1
      7: f11 -> f12 : arg1'=arg1P_8, arg2'=arg2P_8, arg3'=arg3P_8, arg4'=arg4P_8, [ arg3<=arg2 && arg1==arg1P_8 && arg2==arg2P_8 && arg3==arg3P_8 && arg4==arg4P_8 ], cost: 1
      9: f11 -> f14 : arg1'=arg1P_10, arg2'=arg2P_10, arg3'=arg3P_10, arg4'=arg4P_10, [ arg3>arg2 && arg1==arg1P_10 && arg2==arg2P_10 && arg3==arg3P_10 && arg4==arg4P_10 ], cost: 1
      6: f12 -> f13 : arg1'=arg1P_7, arg2'=arg2P_7, arg3'=arg3P_7, arg4'=arg4P_7, [ arg3P_7==arg3+arg1 && arg1==arg1P_7 && arg2==arg2P_7 && arg4==arg4P_7 ], cost: 1
      8: f13 -> f11 : arg1'=arg1P_9, arg2'=arg2P_9, arg3'=arg3P_9, arg4'=arg4P_9, [ arg1==arg1P_9 && arg2==arg2P_9 && arg3==arg3P_9 && arg4==arg4P_9 ], cost: 1
     10: f14 -> f15 : arg1'=arg1P_11, arg2'=arg2P_11, arg3'=arg3P_11, arg4'=arg4P_11, [ arg2P_11==1+arg2 && arg1==arg1P_11 && arg3==arg3P_11 && arg4==arg4P_11 ], cost: 1
     12: f15 -> f9 : arg1'=arg1P_13, arg2'=arg2P_13, arg3'=arg3P_13, arg4'=arg4P_13, [ arg1==arg1P_13 && arg2==arg2P_13 && arg3==arg3P_13 && arg4==arg4P_13 ], cost: 1
     18: __init -> f1 : arg1'=arg1P_19, arg2'=arg2P_19, arg3'=arg3P_19, arg4'=arg4P_19, [], cost: 1

Simplified all rules, resulting in:
   Start location: __init
      0: f1 -> f2 : arg1'=arg1P_1, [], cost: 1
      1: f2 -> f3 : arg2'=arg2P_2, [], cost: 1
      2: f3 -> f4 : arg3'=arg3P_3, [], cost: 1
      3: f4 -> f5 : arg4'=arg4P_4, [], cost: 1
     14: f5 -> f6 : [ arg1>=1 ], cost: 1
      4: f6 -> f9 : arg2'=0, [], cost: 1
     11: f9 -> f10 : [ arg2<arg4 ], cost: 1
      5: f10 -> f11 : arg3'=0, [], cost: 1
      7: f11 -> f12 : [ arg3<=arg2 ], cost: 1
      9: f11 -> f14 : [ arg3>arg2 ], cost: 1
      6: f12 -> f13 : arg3'=arg3+arg1, [], cost: 1
      8: f13 -> f11 : [], cost: 1
     10: f14 -> f15 : arg2'=1+arg2, [], cost: 1
     12: f15 -> f9 : [], cost: 1
     18: __init -> f1 : arg1'=arg1P_19, arg2'=arg2P_19, arg3'=arg3P_19, arg4'=arg4P_19, [], cost: 1

### Simplification by acceleration and chaining ###

Eliminated locations (on linear paths):
   Start location: __init
     25: f9 -> f11 : arg3'=0, [ arg2<arg4 ], cost: 2
     28: f11 -> f11 : arg3'=arg3+arg1, [ arg3<=arg2 ], cost: 3
     29: f11 -> f9 : arg2'=1+arg2, [ arg3>arg2 ], cost: 3
     24: __init -> f9 : arg1'=arg1P_1, arg2'=0, arg3'=arg3P_3, arg4'=arg4P_4, [ arg1P_1>=1 ], cost: 7

Accelerating simple loops of location 8.
   Accelerating the following rules:
     28: f11 -> f11 : arg3'=arg3+arg1, [ arg3<=arg2 ], cost: 3

[test] deduced pseudo-invariant arg1<=0, also trying -arg1<=-1
   Accelerated rule 28 with non-termination, yielding the new rule 30.
   Accelerated rule 28 with non-termination, yielding the new rule 31.
   Accelerated rule 28 with backward acceleration, yielding the new rule 32.
   Accelerated rule 28 with backward acceleration, yielding the new rule 33.
[accelerate] Nesting with 1 inner and 1 outer candidates
   Also removing duplicate rules: 31.

Accelerated all simple loops using metering functions (where possible):
   Start location: __init
     25: f9 -> f11 : arg3'=0, [ arg2<arg4 ], cost: 2
     28: f11 -> f11 : arg3'=arg3+arg1, [ arg3<=arg2 ], cost: 3
     29: f11 -> f9 : arg2'=1+arg2, [ arg3>arg2 ], cost: 3
     30: f11 -> [17] : [ arg3<=arg2 && arg2==0 && arg3==0 && arg1==0 ], cost: NONTERM
     32: f11 -> [17] : [ arg3<=arg2 && arg1<=0 ], cost: NONTERM
     33: f11 -> f11 : arg3'=arg3+k*arg1, [ -arg1<=-1 && k>=0 && (-1+k)*arg1+arg3<=arg2 ], cost: 3*k
     24: __init -> f9 : arg1'=arg1P_1, arg2'=0, arg3'=arg3P_3, arg4'=arg4P_4, [ arg1P_1>=1 ], cost: 7

Chained accelerated rules (with incoming rules):
   Start location: __init
     25: f9 -> f11 : arg3'=0, [ arg2<arg4 ], cost: 2
     34: f9 -> f11 : arg3'=arg1, [ arg2<arg4 && 0<=arg2 ], cost: 5
     35: f9 -> [17] : [ arg2<arg4 && arg2==0 && arg1==0 ], cost: NONTERM
     36: f9 -> [17] : [ arg2<arg4 && 0<=arg2 && arg1<=0 ], cost: NONTERM
     37: f9 -> f11 : arg3'=k*arg1, [ arg2<arg4 && -arg1<=-1 && k>=0 && (-1+k)*arg1<=arg2 ], cost: 2+3*k
     29: f11 -> f9 : arg2'=1+arg2, [ arg3>arg2 ], cost: 3
     24: __init -> f9 : arg1'=arg1P_1, arg2'=0, arg3'=arg3P_3, arg4'=arg4P_4, [ arg1P_1>=1 ], cost: 7

Eliminated locations (on tree-shaped paths):
   Start location: __init
     35: f9 -> [17] : [ arg2<arg4 && arg2==0 && arg1==0 ], cost: NONTERM
     36: f9 -> [17] : [ arg2<arg4 && 0<=arg2 && arg1<=0 ], cost: NONTERM
     38: f9 -> f9 : arg2'=1+arg2, arg3'=0, [ arg2<arg4 && 0>arg2 ], cost: 5
     39: f9 -> f9 : arg2'=1+arg2, arg3'=arg1, [ arg2<arg4 && 0<=arg2 && arg1>arg2 ], cost: 8
     40: f9 -> f9 : arg2'=1+arg2, arg3'=k*arg1, [ arg2<arg4 && -arg1<=-1 && k>=0 && (-1+k)*arg1<=arg2 && k*arg1>arg2 ], cost: 5+3*k
     24: __init -> f9 : arg1'=arg1P_1, arg2'=0, arg3'=arg3P_3, arg4'=arg4P_4, [ arg1P_1>=1 ], cost: 7

Accelerating simple loops of location 6.
   Accelerating the following rules:
     38: f9 -> f9 : arg2'=1+arg2, arg3'=0, [ arg2<arg4 && 0>arg2 ], cost: 5
     39: f9 -> f9 : arg2'=1+arg2, arg3'=arg1, [ arg2<arg4 && 0<=arg2 && arg1>arg2 ], cost: 8
     40: f9 -> f9 : arg2'=1+arg2, arg3'=k*arg1, [ arg2<arg4 && -arg1<=-1 && k>=0 && (-1+k)*arg1<=arg2 && k*arg1>arg2 ], cost: 5+3*k

   Accelerated rule 38 with backward acceleration, yielding the new rule 41.
   Accelerated rule 38 with backward acceleration, yielding the new rule 42.
   Accelerated rule 39 with backward acceleration, yielding the new rule 43.
   Accelerated rule 39 with backward acceleration, yielding the new rule 44.
   Accelerated rule 40 with backward acceleration, yielding the new rule 45.
   Accelerated rule 40 with backward acceleration, yielding the new rule 46.
[accelerate] Nesting with 6 inner and 3 outer candidates
   Removing the simple loops: 38 39 40.

Accelerated all simple loops using metering functions (where possible):
   Start location: __init
     35: f9 -> [17] : [ arg2<arg4 && arg2==0 && arg1==0 ], cost: NONTERM
     36: f9 -> [17] : [ arg2<arg4 && 0<=arg2 && arg1<=0 ], cost: NONTERM
     41: f9 -> f9 : arg2'=arg4, arg3'=0, [ -arg2+arg4>=1 && 0>-1+arg4 ], cost: -5*arg2+5*arg4
     42: f9 -> f9 : arg2'=0, arg3'=0, [ -arg2>=1 && -1<arg4 ], cost: -5*arg2
     43: f9 -> f9 : arg2'=arg4, arg3'=arg1, [ 0<=arg2 && -arg2+arg4>=1 && arg1>-1+arg4 ], cost: -8*arg2+8*arg4
     44: f9 -> f9 : arg2'=arg1, arg3'=arg1, [ 0<=arg2 && -arg2+arg1>=1 && -1+arg1<arg4 ], cost: -8*arg2+8*arg1
     45: f9 -> f9 : arg2'=arg4, arg3'=k*arg1, [ -arg1<=-1 && k>=0 && (-1+k)*arg1<=arg2 && -arg2+arg4>=1 && k*arg1>-1+arg4 ], cost: -5*arg2-3*k*(arg2-arg4)+5*arg4
     46: f9 -> f9 : arg2'=k*arg1, arg3'=k*arg1, [ -arg1<=-1 && k>=0 && (-1+k)*arg1<=arg2 && -arg2+k*arg1>=1 && -1+k*arg1<arg4 ], cost: -5*arg2-3*(arg2-k*arg1)*k+5*k*arg1
     24: __init -> f9 : arg1'=arg1P_1, arg2'=0, arg3'=arg3P_3, arg4'=arg4P_4, [ arg1P_1>=1 ], cost: 7

Chained accelerated rules (with incoming rules):
   Start location: __init
     35: f9 -> [17] : [ arg2<arg4 && arg2==0 && arg1==0 ], cost: NONTERM
     36: f9 -> [17] : [ arg2<arg4 && 0<=arg2 && arg1<=0 ], cost: NONTERM
     24: __init -> f9 : arg1'=arg1P_1, arg2'=0, arg3'=arg3P_3, arg4'=arg4P_4, [ arg1P_1>=1 ], cost: 7
     47: __init -> f9 : arg1'=arg1P_1, arg2'=arg4P_4, arg3'=arg1P_1, arg4'=arg4P_4, [ arg1P_1>=1 && arg4P_4>=1 && arg1P_1>-1+arg4P_4 ], cost: 7+8*arg4P_4
     48: __init -> f9 : arg1'=arg1P_1, arg2'=arg1P_1, arg3'=arg1P_1, arg4'=arg4P_4, [ arg1P_1>=1 && -1+arg1P_1<arg4P_4 ], cost: 7+8*arg1P_1
     49: __init -> f9 : arg1'=arg1P_1, arg2'=arg4P_4, arg3'=arg1P_1*k, arg4'=arg4P_4, [ arg1P_1>=1 && k>=0 && (-1+k)*arg1P_1<=0 && arg4P_4>=1 && arg1P_1*k>-1+arg4P_4 ], cost: 7+5*arg4P_4+3*arg4P_4*k
     50: __init -> f9 : arg1'=arg1P_1, arg2'=arg1P_1*k, arg3'=arg1P_1*k, arg4'=arg4P_4, [ arg1P_1>=1 && k>=0 && (-1+k)*arg1P_1<=0 && arg1P_1*k>=1 && -1+arg1P_1*k<arg4P_4 ], cost: 7+5*arg1P_1*k+3*arg1P_1*k^2

Eliminated locations (on tree-shaped paths):
   Start location: __init
     51: __init -> [19] : [ arg1P_1>=1 && arg4P_4>=1 && arg1P_1>-1+arg4P_4 ], cost: 7+8*arg4P_4
     52: __init -> [19] : [ arg1P_1>=1 && -1+arg1P_1<arg4P_4 ], cost: 7+8*arg1P_1
     53: __init -> [19] : [ arg1P_1>=1 && k>=0 && (-1+k)*arg1P_1<=0 && arg4P_4>=1 && arg1P_1*k>-1+arg4P_4 ], cost: 7+5*arg4P_4+3*arg4P_4*k
     54: __init -> [19] : [ arg1P_1>=1 && k>=0 && (-1+k)*arg1P_1<=0 && arg1P_1*k>=1 && -1+arg1P_1*k<arg4P_4 ], cost: 7+5*arg1P_1*k+3*arg1P_1*k^2

### Computing asymptotic complexity ###

Fully simplified ITS problem
   Start location: __init
     51: __init -> [19] : [ arg1P_1>=1 && arg4P_4>=1 && arg1P_1>-1+arg4P_4 ], cost: 7+8*arg4P_4
     52: __init -> [19] : [ arg1P_1>=1 && -1+arg1P_1<arg4P_4 ], cost: 7+8*arg1P_1
     53: __init -> [19] : [ arg1P_1>=1 && k>=0 && (-1+k)*arg1P_1<=0 && arg4P_4>=1 && arg1P_1*k>-1+arg4P_4 ], cost: 7+5*arg4P_4+3*arg4P_4*k
     54: __init -> [19] : [ arg1P_1>=1 && k>=0 && (-1+k)*arg1P_1<=0 && arg1P_1*k>=1 && -1+arg1P_1*k<arg4P_4 ], cost: 7+5*arg1P_1*k+3*arg1P_1*k^2

Computing asymptotic complexity for rule 54
   Simplified the guard:
     54: __init -> [19] : [ (-1+k)*arg1P_1<=0 && arg1P_1*k>=1 && -1+arg1P_1*k<arg4P_4 ], cost: 7+5*arg1P_1*k+3*arg1P_1*k^2
   Resulting cost 0 has complexity: Unknown

Computing asymptotic complexity for rule 53
   Simplified the guard:
     53: __init -> [19] : [ (-1+k)*arg1P_1<=0 && arg4P_4>=1 && arg1P_1*k>-1+arg4P_4 ], cost: 7+5*arg4P_4+3*arg4P_4*k
   Resulting cost 0 has complexity: Unknown

Computing asymptotic complexity for rule 52
   Resulting cost 0 has complexity: Unknown

Computing asymptotic complexity for rule 51
   Simplified the guard:
     51: __init -> [19] : [ arg4P_4>=1 && arg1P_1>-1+arg4P_4 ], cost: 7+8*arg4P_4
   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),?)