WORST_CASE(Omega(1),?)

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

Initial linear ITS problem
   Start location: l10
      0: l0 -> l1 : i^0'=i^post_1, j^0'=j^post_1, tmp5^0'=tmp5^post_1, x3^0'=x3^post_1, y4^0'=y4^post_1, [ i^0==i^post_1 && j^0==j^post_1 && tmp5^0==tmp5^post_1 && x3^0==x3^post_1 && y4^0==y4^post_1 ], cost: 1
     10: l1 -> l4 : i^0'=i^post_11, j^0'=j^post_11, tmp5^0'=tmp5^post_11, x3^0'=x3^post_11, y4^0'=y4^post_11, [ 1+i^0<=0 && i^0==i^post_11 && j^0==j^post_11 && tmp5^0==tmp5^post_11 && x3^0==x3^post_11 && y4^0==y4^post_11 ], cost: 1
     11: l1 -> l6 : i^0'=i^post_12, j^0'=j^post_12, tmp5^0'=tmp5^post_12, x3^0'=x3^post_12, y4^0'=y4^post_12, [ 0<=i^0 && i^0==i^post_12 && j^0==j^post_12 && tmp5^0==tmp5^post_12 && x3^0==x3^post_12 && y4^0==y4^post_12 ], cost: 1
      1: l2 -> l3 : i^0'=i^post_2, j^0'=j^post_2, tmp5^0'=tmp5^post_2, x3^0'=x3^post_2, y4^0'=y4^post_2, [ i^0==i^post_2 && j^0==j^post_2 && tmp5^0==tmp5^post_2 && x3^0==x3^post_2 && y4^0==y4^post_2 ], cost: 1
      2: l4 -> l2 : i^0'=i^post_3, j^0'=j^post_3, tmp5^0'=tmp5^post_3, x3^0'=x3^post_3, y4^0'=y4^post_3, [ i^0==i^post_3 && j^0==j^post_3 && tmp5^0==tmp5^post_3 && x3^0==x3^post_3 && y4^0==y4^post_3 ], cost: 1
      3: l4 -> l2 : i^0'=i^post_4, j^0'=j^post_4, tmp5^0'=tmp5^post_4, x3^0'=x3^post_4, y4^0'=y4^post_4, [ i^0==i^post_4 && j^0==j^post_4 && tmp5^0==tmp5^post_4 && x3^0==x3^post_4 && y4^0==y4^post_4 ], cost: 1
      4: l5 -> l6 : i^0'=i^post_5, j^0'=j^post_5, tmp5^0'=tmp5^post_5, x3^0'=x3^post_5, y4^0'=y4^post_5, [ j^post_5==1+j^0 && i^0==i^post_5 && tmp5^0==tmp5^post_5 && x3^0==x3^post_5 && y4^0==y4^post_5 ], cost: 1
      5: l6 -> l7 : i^0'=i^post_6, j^0'=j^post_6, tmp5^0'=tmp5^post_6, x3^0'=x3^post_6, y4^0'=y4^post_6, [ i^0==i^post_6 && j^0==j^post_6 && tmp5^0==tmp5^post_6 && x3^0==x3^post_6 && y4^0==y4^post_6 ], cost: 1
      8: l7 -> l0 : i^0'=i^post_9, j^0'=j^post_9, tmp5^0'=tmp5^post_9, x3^0'=x3^post_9, y4^0'=y4^post_9, [ i^0<=j^0 && i^post_9==-1+i^0 && j^0==j^post_9 && tmp5^0==tmp5^post_9 && x3^0==x3^post_9 && y4^0==y4^post_9 ], cost: 1
      9: l7 -> l8 : i^0'=i^post_10, j^0'=j^post_10, tmp5^0'=tmp5^post_10, x3^0'=x3^post_10, y4^0'=y4^post_10, [ 1+j^0<=i^0 && i^0==i^post_10 && j^0==j^post_10 && tmp5^0==tmp5^post_10 && x3^0==x3^post_10 && y4^0==y4^post_10 ], cost: 1
      6: l8 -> l5 : i^0'=i^post_7, j^0'=j^post_7, tmp5^0'=tmp5^post_7, x3^0'=x3^post_7, y4^0'=y4^post_7, [ x3^post_7==j^0 && y4^post_7==1+j^0 && tmp5^post_7==tmp5^post_7 && i^0==i^post_7 && j^0==j^post_7 ], cost: 1
      7: l8 -> l5 : i^0'=i^post_8, j^0'=j^post_8, tmp5^0'=tmp5^post_8, x3^0'=x3^post_8, y4^0'=y4^post_8, [ i^0==i^post_8 && j^0==j^post_8 && tmp5^0==tmp5^post_8 && x3^0==x3^post_8 && y4^0==y4^post_8 ], cost: 1
     12: l9 -> l0 : i^0'=i^post_13, j^0'=j^post_13, tmp5^0'=tmp5^post_13, x3^0'=x3^post_13, y4^0'=y4^post_13, [ j^post_13==0 && i^post_13==4 && tmp5^0==tmp5^post_13 && x3^0==x3^post_13 && y4^0==y4^post_13 ], cost: 1
     13: l10 -> l9 : i^0'=i^post_14, j^0'=j^post_14, tmp5^0'=tmp5^post_14, x3^0'=x3^post_14, y4^0'=y4^post_14, [ i^0==i^post_14 && j^0==j^post_14 && tmp5^0==tmp5^post_14 && x3^0==x3^post_14 && y4^0==y4^post_14 ], cost: 1

Checking for constant complexity:
   The following rule is satisfiable with cost >= 1, yielding constant complexity:
     13: l10 -> l9 : i^0'=i^post_14, j^0'=j^post_14, tmp5^0'=tmp5^post_14, x3^0'=x3^post_14, y4^0'=y4^post_14, [ i^0==i^post_14 && j^0==j^post_14 && tmp5^0==tmp5^post_14 && x3^0==x3^post_14 && y4^0==y4^post_14 ], cost: 1

Removed unreachable and leaf rules:
   Start location: l10
      0: l0 -> l1 : i^0'=i^post_1, j^0'=j^post_1, tmp5^0'=tmp5^post_1, x3^0'=x3^post_1, y4^0'=y4^post_1, [ i^0==i^post_1 && j^0==j^post_1 && tmp5^0==tmp5^post_1 && x3^0==x3^post_1 && y4^0==y4^post_1 ], cost: 1
     11: l1 -> l6 : i^0'=i^post_12, j^0'=j^post_12, tmp5^0'=tmp5^post_12, x3^0'=x3^post_12, y4^0'=y4^post_12, [ 0<=i^0 && i^0==i^post_12 && j^0==j^post_12 && tmp5^0==tmp5^post_12 && x3^0==x3^post_12 && y4^0==y4^post_12 ], cost: 1
      4: l5 -> l6 : i^0'=i^post_5, j^0'=j^post_5, tmp5^0'=tmp5^post_5, x3^0'=x3^post_5, y4^0'=y4^post_5, [ j^post_5==1+j^0 && i^0==i^post_5 && tmp5^0==tmp5^post_5 && x3^0==x3^post_5 && y4^0==y4^post_5 ], cost: 1
      5: l6 -> l7 : i^0'=i^post_6, j^0'=j^post_6, tmp5^0'=tmp5^post_6, x3^0'=x3^post_6, y4^0'=y4^post_6, [ i^0==i^post_6 && j^0==j^post_6 && tmp5^0==tmp5^post_6 && x3^0==x3^post_6 && y4^0==y4^post_6 ], cost: 1
      8: l7 -> l0 : i^0'=i^post_9, j^0'=j^post_9, tmp5^0'=tmp5^post_9, x3^0'=x3^post_9, y4^0'=y4^post_9, [ i^0<=j^0 && i^post_9==-1+i^0 && j^0==j^post_9 && tmp5^0==tmp5^post_9 && x3^0==x3^post_9 && y4^0==y4^post_9 ], cost: 1
      9: l7 -> l8 : i^0'=i^post_10, j^0'=j^post_10, tmp5^0'=tmp5^post_10, x3^0'=x3^post_10, y4^0'=y4^post_10, [ 1+j^0<=i^0 && i^0==i^post_10 && j^0==j^post_10 && tmp5^0==tmp5^post_10 && x3^0==x3^post_10 && y4^0==y4^post_10 ], cost: 1
      6: l8 -> l5 : i^0'=i^post_7, j^0'=j^post_7, tmp5^0'=tmp5^post_7, x3^0'=x3^post_7, y4^0'=y4^post_7, [ x3^post_7==j^0 && y4^post_7==1+j^0 && tmp5^post_7==tmp5^post_7 && i^0==i^post_7 && j^0==j^post_7 ], cost: 1
      7: l8 -> l5 : i^0'=i^post_8, j^0'=j^post_8, tmp5^0'=tmp5^post_8, x3^0'=x3^post_8, y4^0'=y4^post_8, [ i^0==i^post_8 && j^0==j^post_8 && tmp5^0==tmp5^post_8 && x3^0==x3^post_8 && y4^0==y4^post_8 ], cost: 1
     12: l9 -> l0 : i^0'=i^post_13, j^0'=j^post_13, tmp5^0'=tmp5^post_13, x3^0'=x3^post_13, y4^0'=y4^post_13, [ j^post_13==0 && i^post_13==4 && tmp5^0==tmp5^post_13 && x3^0==x3^post_13 && y4^0==y4^post_13 ], cost: 1
     13: l10 -> l9 : i^0'=i^post_14, j^0'=j^post_14, tmp5^0'=tmp5^post_14, x3^0'=x3^post_14, y4^0'=y4^post_14, [ i^0==i^post_14 && j^0==j^post_14 && tmp5^0==tmp5^post_14 && x3^0==x3^post_14 && y4^0==y4^post_14 ], cost: 1

Simplified all rules, resulting in:
   Start location: l10
      0: l0 -> l1 : [], cost: 1
     11: l1 -> l6 : [ 0<=i^0 ], cost: 1
      4: l5 -> l6 : j^0'=1+j^0, [], cost: 1
      5: l6 -> l7 : [], cost: 1
      8: l7 -> l0 : i^0'=-1+i^0, [ i^0<=j^0 ], cost: 1
      9: l7 -> l8 : [ 1+j^0<=i^0 ], cost: 1
      6: l8 -> l5 : tmp5^0'=tmp5^post_7, x3^0'=j^0, y4^0'=1+j^0, [], cost: 1
      7: l8 -> l5 : [], cost: 1
     12: l9 -> l0 : i^0'=4, j^0'=0, [], cost: 1
     13: l10 -> l9 : [], cost: 1

### Simplification by acceleration and chaining ###

Eliminated locations (on linear paths):
   Start location: l10
     15: l0 -> l6 : [ 0<=i^0 ], cost: 2
      4: l5 -> l6 : j^0'=1+j^0, [], cost: 1
      5: l6 -> l7 : [], cost: 1
      8: l7 -> l0 : i^0'=-1+i^0, [ i^0<=j^0 ], cost: 1
      9: l7 -> l8 : [ 1+j^0<=i^0 ], cost: 1
      6: l8 -> l5 : tmp5^0'=tmp5^post_7, x3^0'=j^0, y4^0'=1+j^0, [], cost: 1
      7: l8 -> l5 : [], cost: 1
     14: l10 -> l0 : i^0'=4, j^0'=0, [], cost: 2

Eliminated locations (on tree-shaped paths):
   Start location: l10
     15: l0 -> l6 : [ 0<=i^0 ], cost: 2
     16: l6 -> l0 : i^0'=-1+i^0, [ i^0<=j^0 ], cost: 2
     17: l6 -> l8 : [ 1+j^0<=i^0 ], cost: 2
     18: l8 -> l6 : j^0'=1+j^0, tmp5^0'=tmp5^post_7, x3^0'=j^0, y4^0'=1+j^0, [], cost: 2
     19: l8 -> l6 : j^0'=1+j^0, [], cost: 2
     14: l10 -> l0 : i^0'=4, j^0'=0, [], cost: 2

Eliminated locations (on tree-shaped paths):
   Start location: l10
     15: l0 -> l6 : [ 0<=i^0 ], cost: 2
     16: l6 -> l0 : i^0'=-1+i^0, [ i^0<=j^0 ], cost: 2
     20: l6 -> l6 : j^0'=1+j^0, tmp5^0'=tmp5^post_7, x3^0'=j^0, y4^0'=1+j^0, [ 1+j^0<=i^0 ], cost: 4
     21: l6 -> l6 : j^0'=1+j^0, [ 1+j^0<=i^0 ], cost: 4
     14: l10 -> l0 : i^0'=4, j^0'=0, [], cost: 2

Accelerating simple loops of location 6.
   Accelerating the following rules:
     20: l6 -> l6 : j^0'=1+j^0, tmp5^0'=tmp5^post_7, x3^0'=j^0, y4^0'=1+j^0, [ 1+j^0<=i^0 ], cost: 4
     21: l6 -> l6 : j^0'=1+j^0, [ 1+j^0<=i^0 ], cost: 4

   Accelerated rule 20 with metering function i^0-j^0, yielding the new rule 22.
   Accelerated rule 21 with metering function i^0-j^0, yielding the new rule 23.
   Removing the simple loops: 20 21.

Accelerated all simple loops using metering functions (where possible):
   Start location: l10
     15: l0 -> l6 : [ 0<=i^0 ], cost: 2
     16: l6 -> l0 : i^0'=-1+i^0, [ i^0<=j^0 ], cost: 2
     22: l6 -> l6 : j^0'=i^0, tmp5^0'=tmp5^post_7, x3^0'=-1+i^0, y4^0'=i^0, [ 1+j^0<=i^0 ], cost: 4*i^0-4*j^0
     23: l6 -> l6 : j^0'=i^0, [ 1+j^0<=i^0 ], cost: 4*i^0-4*j^0
     14: l10 -> l0 : i^0'=4, j^0'=0, [], cost: 2

Chained accelerated rules (with incoming rules):
   Start location: l10
     15: l0 -> l6 : [ 0<=i^0 ], cost: 2
     24: l0 -> l6 : j^0'=i^0, tmp5^0'=tmp5^post_7, x3^0'=-1+i^0, y4^0'=i^0, [ 0<=i^0 && 1+j^0<=i^0 ], cost: 2+4*i^0-4*j^0
     25: l0 -> l6 : j^0'=i^0, [ 0<=i^0 && 1+j^0<=i^0 ], cost: 2+4*i^0-4*j^0
     16: l6 -> l0 : i^0'=-1+i^0, [ i^0<=j^0 ], cost: 2
     14: l10 -> l0 : i^0'=4, j^0'=0, [], cost: 2

Eliminated locations (on tree-shaped paths):
   Start location: l10
     26: l0 -> l0 : i^0'=-1+i^0, [ 0<=i^0 && i^0<=j^0 ], cost: 4
     27: l0 -> l0 : i^0'=-1+i^0, j^0'=i^0, tmp5^0'=tmp5^post_7, x3^0'=-1+i^0, y4^0'=i^0, [ 0<=i^0 && 1+j^0<=i^0 ], cost: 4+4*i^0-4*j^0
     28: l0 -> l0 : i^0'=-1+i^0, j^0'=i^0, [ 0<=i^0 && 1+j^0<=i^0 ], cost: 4+4*i^0-4*j^0
     14: l10 -> l0 : i^0'=4, j^0'=0, [], cost: 2

Accelerating simple loops of location 0.
   Accelerating the following rules:
     26: l0 -> l0 : i^0'=-1+i^0, [ 0<=i^0 && i^0<=j^0 ], cost: 4
     27: l0 -> l0 : i^0'=-1+i^0, j^0'=i^0, tmp5^0'=tmp5^post_7, x3^0'=-1+i^0, y4^0'=i^0, [ 0<=i^0 && 1+j^0<=i^0 ], cost: 4+4*i^0-4*j^0
     28: l0 -> l0 : i^0'=-1+i^0, j^0'=i^0, [ 0<=i^0 && 1+j^0<=i^0 ], cost: 4+4*i^0-4*j^0

   Accelerated rule 26 with metering function 1+i^0, yielding the new rule 29.
   Found no metering function for rule 27.
   Found no metering function for rule 28.
   Removing the simple loops: 26.

Accelerated all simple loops using metering functions (where possible):
   Start location: l10
     27: l0 -> l0 : i^0'=-1+i^0, j^0'=i^0, tmp5^0'=tmp5^post_7, x3^0'=-1+i^0, y4^0'=i^0, [ 0<=i^0 && 1+j^0<=i^0 ], cost: 4+4*i^0-4*j^0
     28: l0 -> l0 : i^0'=-1+i^0, j^0'=i^0, [ 0<=i^0 && 1+j^0<=i^0 ], cost: 4+4*i^0-4*j^0
     29: l0 -> l0 : i^0'=-1, [ 0<=i^0 && i^0<=j^0 ], cost: 4+4*i^0
     14: l10 -> l0 : i^0'=4, j^0'=0, [], cost: 2

Chained accelerated rules (with incoming rules):
   Start location: l10
     14: l10 -> l0 : i^0'=4, j^0'=0, [], cost: 2
     30: l10 -> l0 : i^0'=3, j^0'=4, tmp5^0'=tmp5^post_7, x3^0'=3, y4^0'=4, [], cost: 22
     31: l10 -> l0 : i^0'=3, j^0'=4, [], cost: 22

Removed unreachable locations (and leaf rules with constant cost):
   Start location: l10
     <empty>

### Computing asymptotic complexity ###

Fully simplified ITS problem
   Start location: l10
     <empty>

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:  [ i^0==i^post_14 && j^0==j^post_14 && tmp5^0==tmp5^post_14 && x3^0==x3^post_14 && y4^0==y4^post_14 ]

WORST_CASE(Omega(1),?)