WORST_CASE(Omega(n^2),?)

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

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

Checking for constant complexity:
   The following rule is satisfiable with cost >= 1, yielding constant complexity:
     12: l9 -> l8 : guard^0'=guard^post_13, i^0'=i^post_13, j^0'=j^post_13, n^0'=n^post_13, [ guard^0==guard^post_13 && i^0==i^post_13 && j^0==j^post_13 && n^0==n^post_13 ], cost: 1

Removed unreachable and leaf rules:
   Start location: l9
      0: l0 -> l1 : guard^0'=guard^post_1, i^0'=i^post_1, j^0'=j^post_1, n^0'=n^post_1, [ n^0<=j^0 && i^post_1==1+i^0 && guard^0==guard^post_1 && j^0==j^post_1 && n^0==n^post_1 ], cost: 1
      1: l0 -> l2 : guard^0'=guard^post_2, i^0'=i^post_2, j^0'=j^post_2, n^0'=n^post_2, [ 1+j^0<=n^0 && guard^post_2==guard^post_2 && i^0==i^post_2 && j^0==j^post_2 && n^0==n^post_2 ], cost: 1
      4: l1 -> l3 : guard^0'=guard^post_5, i^0'=i^post_5, j^0'=j^post_5, n^0'=n^post_5, [ guard^0==guard^post_5 && i^0==i^post_5 && j^0==j^post_5 && n^0==n^post_5 ], cost: 1
      8: l2 -> l6 : guard^0'=guard^post_9, i^0'=i^post_9, j^0'=j^post_9, n^0'=n^post_9, [ guard^0<=0 && 0<=guard^0 && guard^0==guard^post_9 && i^0==i^post_9 && j^0==j^post_9 && n^0==n^post_9 ], cost: 1
      9: l2 -> l7 : guard^0'=guard^post_10, i^0'=i^post_10, j^0'=j^post_10, n^0'=n^post_10, [ 1<=guard^0 && guard^0==guard^post_10 && i^0==i^post_10 && j^0==j^post_10 && n^0==n^post_10 ], cost: 1
     10: l2 -> l7 : guard^0'=guard^post_11, i^0'=i^post_11, j^0'=j^post_11, n^0'=n^post_11, [ 1+guard^0<=0 && guard^0==guard^post_11 && i^0==i^post_11 && j^0==j^post_11 && n^0==n^post_11 ], cost: 1
      3: l3 -> l5 : guard^0'=guard^post_4, i^0'=i^post_4, j^0'=j^post_4, n^0'=n^post_4, [ 1+i^0<=n^0 && j^post_4==1+i^0 && guard^0==guard^post_4 && i^0==i^post_4 && n^0==n^post_4 ], cost: 1
      5: l5 -> l0 : guard^0'=guard^post_6, i^0'=i^post_6, j^0'=j^post_6, n^0'=n^post_6, [ guard^0==guard^post_6 && i^0==i^post_6 && j^0==j^post_6 && n^0==n^post_6 ], cost: 1
      6: l6 -> l5 : guard^0'=guard^post_7, i^0'=i^post_7, j^0'=j^post_7, n^0'=n^post_7, [ j^post_7==1+j^0 && guard^0==guard^post_7 && i^0==i^post_7 && n^0==n^post_7 ], cost: 1
      7: l7 -> l6 : guard^0'=guard^post_8, i^0'=i^post_8, j^0'=j^post_8, n^0'=n^post_8, [ j^post_8==-1+j^0 && n^post_8==-1+n^0 && guard^0==guard^post_8 && i^0==i^post_8 ], cost: 1
     11: l8 -> l1 : guard^0'=guard^post_12, i^0'=i^post_12, j^0'=j^post_12, n^0'=n^post_12, [ i^post_12==0 && guard^0==guard^post_12 && j^0==j^post_12 && n^0==n^post_12 ], cost: 1
     12: l9 -> l8 : guard^0'=guard^post_13, i^0'=i^post_13, j^0'=j^post_13, n^0'=n^post_13, [ guard^0==guard^post_13 && i^0==i^post_13 && j^0==j^post_13 && n^0==n^post_13 ], cost: 1

Simplified all rules, resulting in:
   Start location: l9
      0: l0 -> l1 : i^0'=1+i^0, [ n^0<=j^0 ], cost: 1
      1: l0 -> l2 : guard^0'=guard^post_2, [ 1+j^0<=n^0 ], cost: 1
      4: l1 -> l3 : [], cost: 1
      8: l2 -> l6 : [ guard^0==0 ], cost: 1
      9: l2 -> l7 : [ 1<=guard^0 ], cost: 1
     10: l2 -> l7 : [ 1+guard^0<=0 ], cost: 1
      3: l3 -> l5 : j^0'=1+i^0, [ 1+i^0<=n^0 ], cost: 1
      5: l5 -> l0 : [], cost: 1
      6: l6 -> l5 : j^0'=1+j^0, [], cost: 1
      7: l7 -> l6 : j^0'=-1+j^0, n^0'=-1+n^0, [], cost: 1
     11: l8 -> l1 : i^0'=0, [], cost: 1
     12: l9 -> l8 : [], cost: 1

### Simplification by acceleration and chaining ###

Eliminated locations (on linear paths):
   Start location: l9
      0: l0 -> l1 : i^0'=1+i^0, [ n^0<=j^0 ], cost: 1
      1: l0 -> l2 : guard^0'=guard^post_2, [ 1+j^0<=n^0 ], cost: 1
     14: l1 -> l5 : j^0'=1+i^0, [ 1+i^0<=n^0 ], cost: 2
      8: l2 -> l6 : [ guard^0==0 ], cost: 1
      9: l2 -> l7 : [ 1<=guard^0 ], cost: 1
     10: l2 -> l7 : [ 1+guard^0<=0 ], cost: 1
      5: l5 -> l0 : [], cost: 1
      6: l6 -> l5 : j^0'=1+j^0, [], cost: 1
      7: l7 -> l6 : j^0'=-1+j^0, n^0'=-1+n^0, [], cost: 1
     13: l9 -> l1 : i^0'=0, [], cost: 2

Eliminated locations (on tree-shaped paths):
   Start location: l9
     14: l1 -> l5 : j^0'=1+i^0, [ 1+i^0<=n^0 ], cost: 2
      8: l2 -> l6 : [ guard^0==0 ], cost: 1
     17: l2 -> l6 : j^0'=-1+j^0, n^0'=-1+n^0, [ 1<=guard^0 ], cost: 2
     18: l2 -> l6 : j^0'=-1+j^0, n^0'=-1+n^0, [ 1+guard^0<=0 ], cost: 2
     15: l5 -> l1 : i^0'=1+i^0, [ n^0<=j^0 ], cost: 2
     16: l5 -> l2 : guard^0'=guard^post_2, [ 1+j^0<=n^0 ], cost: 2
      6: l6 -> l5 : j^0'=1+j^0, [], cost: 1
     13: l9 -> l1 : i^0'=0, [], cost: 2

Eliminated locations (on tree-shaped paths):
   Start location: l9
     14: l1 -> l5 : j^0'=1+i^0, [ 1+i^0<=n^0 ], cost: 2
     15: l5 -> l1 : i^0'=1+i^0, [ n^0<=j^0 ], cost: 2
     19: l5 -> l6 : guard^0'=guard^post_2, [ 1+j^0<=n^0 && guard^post_2==0 ], cost: 3
     20: l5 -> l6 : guard^0'=guard^post_2, j^0'=-1+j^0, n^0'=-1+n^0, [ 1+j^0<=n^0 && 1<=guard^post_2 ], cost: 4
     21: l5 -> l6 : guard^0'=guard^post_2, j^0'=-1+j^0, n^0'=-1+n^0, [ 1+j^0<=n^0 && 1+guard^post_2<=0 ], cost: 4
      6: l6 -> l5 : j^0'=1+j^0, [], cost: 1
     13: l9 -> l1 : i^0'=0, [], cost: 2

Eliminated locations (on tree-shaped paths):
   Start location: l9
     14: l1 -> l5 : j^0'=1+i^0, [ 1+i^0<=n^0 ], cost: 2
     15: l5 -> l1 : i^0'=1+i^0, [ n^0<=j^0 ], cost: 2
     22: l5 -> l5 : guard^0'=guard^post_2, j^0'=1+j^0, [ 1+j^0<=n^0 && guard^post_2==0 ], cost: 4
     23: l5 -> l5 : guard^0'=guard^post_2, j^0'=j^0, n^0'=-1+n^0, [ 1+j^0<=n^0 && 1<=guard^post_2 ], cost: 5
     24: l5 -> l5 : guard^0'=guard^post_2, j^0'=j^0, n^0'=-1+n^0, [ 1+j^0<=n^0 && 1+guard^post_2<=0 ], cost: 5
     13: l9 -> l1 : i^0'=0, [], cost: 2

Accelerating simple loops of location 5.
   Simplified some of the simple loops (and removed duplicate rules).
   Accelerating the following rules:
     22: l5 -> l5 : guard^0'=0, j^0'=1+j^0, [ 1+j^0<=n^0 ], cost: 4
     23: l5 -> l5 : guard^0'=guard^post_2, n^0'=-1+n^0, [ 1+j^0<=n^0 && 1<=guard^post_2 ], cost: 5
     24: l5 -> l5 : guard^0'=guard^post_2, n^0'=-1+n^0, [ 1+j^0<=n^0 && 1+guard^post_2<=0 ], cost: 5

   Accelerated rule 22 with metering function -j^0+n^0, yielding the new rule 25.
   Accelerated rule 23 with metering function -j^0+n^0, yielding the new rule 26.
   Accelerated rule 24 with metering function -j^0+n^0, yielding the new rule 27.
   Removing the simple loops: 22 23 24.

Accelerated all simple loops using metering functions (where possible):
   Start location: l9
     14: l1 -> l5 : j^0'=1+i^0, [ 1+i^0<=n^0 ], cost: 2
     15: l5 -> l1 : i^0'=1+i^0, [ n^0<=j^0 ], cost: 2
     25: l5 -> l5 : guard^0'=0, j^0'=n^0, [ 1+j^0<=n^0 ], cost: -4*j^0+4*n^0
     26: l5 -> l5 : guard^0'=guard^post_2, n^0'=j^0, [ 1+j^0<=n^0 && 1<=guard^post_2 ], cost: -5*j^0+5*n^0
     27: l5 -> l5 : guard^0'=guard^post_2, n^0'=j^0, [ 1+j^0<=n^0 && 1+guard^post_2<=0 ], cost: -5*j^0+5*n^0
     13: l9 -> l1 : i^0'=0, [], cost: 2

Chained accelerated rules (with incoming rules):
   Start location: l9
     14: l1 -> l5 : j^0'=1+i^0, [ 1+i^0<=n^0 ], cost: 2
     28: l1 -> l5 : guard^0'=0, j^0'=n^0, [ 2+i^0<=n^0 ], cost: -2+4*n^0-4*i^0
     29: l1 -> l5 : guard^0'=guard^post_2, j^0'=1+i^0, n^0'=1+i^0, [ 2+i^0<=n^0 && 1<=guard^post_2 ], cost: -3+5*n^0-5*i^0
     30: l1 -> l5 : guard^0'=guard^post_2, j^0'=1+i^0, n^0'=1+i^0, [ 2+i^0<=n^0 && 1+guard^post_2<=0 ], cost: -3+5*n^0-5*i^0
     15: l5 -> l1 : i^0'=1+i^0, [ n^0<=j^0 ], cost: 2
     13: l9 -> l1 : i^0'=0, [], cost: 2

Eliminated locations (on tree-shaped paths):
   Start location: l9
     31: l1 -> l1 : i^0'=1+i^0, j^0'=1+i^0, [ 1+i^0<=n^0 && n^0<=1+i^0 ], cost: 4
     32: l1 -> l1 : guard^0'=0, i^0'=1+i^0, j^0'=n^0, [ 2+i^0<=n^0 ], cost: 4*n^0-4*i^0
     33: l1 -> l1 : guard^0'=guard^post_2, i^0'=1+i^0, j^0'=1+i^0, n^0'=1+i^0, [ 2+i^0<=n^0 && 1<=guard^post_2 ], cost: -1+5*n^0-5*i^0
     34: l1 -> l1 : guard^0'=guard^post_2, i^0'=1+i^0, j^0'=1+i^0, n^0'=1+i^0, [ 2+i^0<=n^0 && 1+guard^post_2<=0 ], cost: -1+5*n^0-5*i^0
     13: l9 -> l1 : i^0'=0, [], cost: 2

Accelerating simple loops of location 1.
   Simplified some of the simple loops (and removed duplicate rules).
   Accelerating the following rules:
     31: l1 -> l1 : i^0'=1+i^0, j^0'=1+i^0, [ 1-n^0+i^0==0 ], cost: 4
     32: l1 -> l1 : guard^0'=0, i^0'=1+i^0, j^0'=n^0, [ 2+i^0<=n^0 ], cost: 4*n^0-4*i^0
     33: l1 -> l1 : guard^0'=guard^post_2, i^0'=1+i^0, j^0'=1+i^0, n^0'=1+i^0, [ 2+i^0<=n^0 && 1<=guard^post_2 ], cost: -1+5*n^0-5*i^0
     34: l1 -> l1 : guard^0'=guard^post_2, i^0'=1+i^0, j^0'=1+i^0, n^0'=1+i^0, [ 2+i^0<=n^0 && 1+guard^post_2<=0 ], cost: -1+5*n^0-5*i^0

   Accelerated rule 31 with metering function n^0-i^0, yielding the new rule 35.
   Accelerated rule 32 with metering function -1+n^0-i^0, yielding the new rule 36.
   Found no metering function for rule 33.
   Found no metering function for rule 34.
   Removing the simple loops: 31 32.

Accelerated all simple loops using metering functions (where possible):
   Start location: l9
     33: l1 -> l1 : guard^0'=guard^post_2, i^0'=1+i^0, j^0'=1+i^0, n^0'=1+i^0, [ 2+i^0<=n^0 && 1<=guard^post_2 ], cost: -1+5*n^0-5*i^0
     34: l1 -> l1 : guard^0'=guard^post_2, i^0'=1+i^0, j^0'=1+i^0, n^0'=1+i^0, [ 2+i^0<=n^0 && 1+guard^post_2<=0 ], cost: -1+5*n^0-5*i^0
     35: l1 -> l1 : i^0'=n^0, j^0'=n^0, [ 1-n^0+i^0==0 ], cost: 4*n^0-4*i^0
     36: l1 -> l1 : guard^0'=0, i^0'=-1+n^0, j^0'=n^0, [ 2+i^0<=n^0 ], cost: -2-2*(-1+n^0-i^0)^2-4*(-1+n^0-i^0)*i^0+2*n^0+4*n^0*(-1+n^0-i^0)-2*i^0
     13: l9 -> l1 : i^0'=0, [], cost: 2

Chained accelerated rules (with incoming rules):
   Start location: l9
     13: l9 -> l1 : i^0'=0, [], cost: 2
     37: l9 -> l1 : guard^0'=guard^post_2, i^0'=1, j^0'=1, n^0'=1, [ 2<=n^0 && 1<=guard^post_2 ], cost: 1+5*n^0
     38: l9 -> l1 : guard^0'=guard^post_2, i^0'=1, j^0'=1, n^0'=1, [ 2<=n^0 && 1+guard^post_2<=0 ], cost: 1+5*n^0
     39: l9 -> l1 : i^0'=n^0, j^0'=n^0, [ 1-n^0==0 ], cost: 2+4*n^0
     40: l9 -> l1 : guard^0'=0, i^0'=-1+n^0, j^0'=n^0, [ 2<=n^0 ], cost: -2*(-1+n^0)^2+2*n^0+4*(-1+n^0)*n^0

Removed unreachable locations (and leaf rules with constant cost):
   Start location: l9
     37: l9 -> l1 : guard^0'=guard^post_2, i^0'=1, j^0'=1, n^0'=1, [ 2<=n^0 && 1<=guard^post_2 ], cost: 1+5*n^0
     38: l9 -> l1 : guard^0'=guard^post_2, i^0'=1, j^0'=1, n^0'=1, [ 2<=n^0 && 1+guard^post_2<=0 ], cost: 1+5*n^0
     39: l9 -> l1 : i^0'=n^0, j^0'=n^0, [ 1-n^0==0 ], cost: 2+4*n^0
     40: l9 -> l1 : guard^0'=0, i^0'=-1+n^0, j^0'=n^0, [ 2<=n^0 ], cost: -2*(-1+n^0)^2+2*n^0+4*(-1+n^0)*n^0

### Computing asymptotic complexity ###

Fully simplified ITS problem
   Start location: l9
     37: l9 -> l1 : guard^0'=guard^post_2, i^0'=1, j^0'=1, n^0'=1, [ 2<=n^0 && 1<=guard^post_2 ], cost: 1+5*n^0
     38: l9 -> l1 : guard^0'=guard^post_2, i^0'=1, j^0'=1, n^0'=1, [ 2<=n^0 && 1+guard^post_2<=0 ], cost: 1+5*n^0
     39: l9 -> l1 : i^0'=n^0, j^0'=n^0, [ 1-n^0==0 ], cost: 2+4*n^0
     40: l9 -> l1 : guard^0'=0, i^0'=-1+n^0, j^0'=n^0, [ 2<=n^0 ], cost: -2*(-1+n^0)^2+2*n^0+4*(-1+n^0)*n^0

Computing asymptotic complexity for rule 37
   Solved the limit problem by the following transformations:
      Created initial limit problem:
      1+5*n^0 (+), guard^post_2 (+/+!), -1+n^0 (+/+!) [not solved]

      removing all constraints (solved by SMT)
      resulting limit problem: [solved]

      applying transformation rule (C) using substitution {guard^post_2==n,n^0==n}
      resulting limit problem:
      [solved]

   Solution:
      guard^post_2 / n
      n^0 / n
   Resulting cost 1+5*n has complexity: Poly(n^1)

Found new complexity Poly(n^1).

Computing asymptotic complexity for rule 40
   Solved the limit problem by the following transformations:
      Created initial limit problem:
      -2+2*n^0^2+2*n^0 (+), -1+n^0 (+/+!) [not solved]

      removing all constraints (solved by SMT)
      resulting limit problem: [solved]

      applying transformation rule (C) using substitution {n^0==n}
      resulting limit problem:
      [solved]

   Solution:
      n^0 / n
   Resulting cost -2+2*n+2*n^2 has complexity: Poly(n^2)

Found new complexity Poly(n^2).

Obtained the following overall complexity (w.r.t. the length of the input n):
   Complexity:  Poly(n^2)
   Cpx degree:  2
   Solved cost: -2+2*n+2*n^2
   Rule cost:   -2*(-1+n^0)^2+2*n^0+4*(-1+n^0)*n^0
   Rule guard:  [ 2<=n^0 ]

WORST_CASE(Omega(n^2),?)