WORST_CASE(Omega(1),?)

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

Initial linear ITS problem
   Start location: l3
      0: l0 -> l1 : c1^0'=c1^post_1, c2^0'=c2^post_1, m^0'=m^post_1, max^0'=max^post_1, n^0'=n^post_1, pi^0'=pi^post_1, pos^0'=pos^post_1, seq^0'=seq^post_1, wpos^0'=wpos^post_1, z^0'=z^post_1, [ 1<=m^0 && c1^1_1==c1^1_1 && 0<=c1^1_1 && c1^1_1<=1 && z^0<=0 && 1<=pos^0 && pos^0<=1 && wpos^0<=0 && 1<=c1^1_1 && wpos^1_1==1+wpos^0 && 1<=c1^1_1 && c2^1_1==c2^1_1 && 0<=c2^1_1 && c2^1_1<=1 && z^0<=0 && 1<=pos^0 && pos^0<=1 && 1<=wpos^1_1 && wpos^1_1<=1 && 1<=pi^0 && c2^1_1<=0 && wpos^2_1==0 && pi^1_1==-1+pi^0 && 1+c2^1_1<=1 && m^1_1==-1+m^0 && 1<=m^1_1 && c1^2_1==c1^2_1 && 0<=c1^2_1 && c1^2_1<=1 && z^0<=0 && 1<=pos^0 && pos^0<=1 && wpos^2_1<=0 && 1<=c1^2_1 && wpos^3_1==1+wpos^2_1 && 1<=c1^2_1 && c2^2_1==c2^2_1 && 0<=c2^2_1 && c2^2_1<=1 && z^0<=0 && 1<=pos^0 && pos^0<=1 && 1<=wpos^3_1 && wpos^3_1<=1 && pi^1_1<=0 && seq^post_1==1+seq^0 && wpos^4_1==0 && pos^1_1==0 && pi^2_1==seq^post_1 && z^1_1==z^1_1 && 0<=z^1_1 && 1<=c2^2_1 && 1+m^1_1<=max^0 && m^2_1==1+m^1_1 && 1<=m^2_1 && c1^3_1==c1^3_1 && 0<=c1^3_1 && c1^3_1<=1 && 1<=z^1_1 && z^2_1==-1+z^1_1 && 1<=c1^3_1 && c2^3_1==c2^3_1 && 0<=c2^3_1 && c2^3_1<=1 && 1<=z^2_1 && z^post_1==-1+z^2_1 && 1<=c2^3_1 && 1+m^2_1<=max^0 && m^3_1==1+m^2_1 && 1<=m^3_1 && c1^4_1==c1^4_1 && 0<=c1^4_1 && c1^4_1<=1 && z^post_1<=0 && pos^1_1<=0 && c1^4_1<=0 && pos^post_1==1+pos^1_1 && 1+c1^4_1<=1 && 1<=m^3_1 && c1^post_1==c1^post_1 && 0<=c1^post_1 && c1^post_1<=1 && z^post_1<=0 && 1<=pos^post_1 && pos^post_1<=1 && wpos^4_1<=0 && 1<=c1^post_1 && wpos^5_1==1+wpos^4_1 && 1<=c1^post_1 && c2^post_1==c2^post_1 && 0<=c2^post_1 && c2^post_1<=1 && z^post_1<=0 && 1<=pos^post_1 && pos^post_1<=1 && 1<=wpos^5_1 && wpos^5_1<=1 && 1<=pi^2_1 && c2^post_1<=0 && wpos^post_1==0 && pi^post_1==-1+pi^2_1 && 1+c2^post_1<=1 && m^post_1==-1+m^3_1 && max^0==max^post_1 && n^0==n^post_1 ], cost: 1
      1: l1 -> l0 : c1^0'=c1^post_2, c2^0'=c2^post_2, m^0'=m^post_2, max^0'=max^post_2, n^0'=n^post_2, pi^0'=pi^post_2, pos^0'=pos^post_2, seq^0'=seq^post_2, wpos^0'=wpos^post_2, z^0'=z^post_2, [ c1^0==c1^post_2 && c2^0==c2^post_2 && m^0==m^post_2 && max^0==max^post_2 && n^0==n^post_2 && pi^0==pi^post_2 && pos^0==pos^post_2 && seq^0==seq^post_2 && wpos^0==wpos^post_2 && z^0==z^post_2 ], cost: 1
      2: l2 -> l0 : c1^0'=c1^post_3, c2^0'=c2^post_3, m^0'=m^post_3, max^0'=max^post_3, n^0'=n^post_3, pi^0'=pi^post_3, pos^0'=pos^post_3, seq^0'=seq^post_3, wpos^0'=wpos^post_3, z^0'=z^post_3, [ seq^post_3==1 && wpos^post_3==0 && pi^post_3==seq^post_3 && z^post_3==z^post_3 && 0<=z^post_3 && pos^1_2==0 && n^post_3==n^post_3 && 0<=n^post_3 && max^post_3==max^post_3 && 0<=max^post_3 && max^post_3<=n^post_3 && m^post_3==m^post_3 && m^post_3<=max^post_3 && 0<=m^post_3 && 1<=m^post_3 && c1^post_3==c1^post_3 && 0<=c1^post_3 && c1^post_3<=1 && z^post_3<=0 && pos^1_2<=0 && c1^post_3<=0 && pos^post_3==1+pos^1_2 && 1+c1^post_3<=1 && c2^0==c2^post_3 ], cost: 1
      3: l3 -> l2 : c1^0'=c1^post_4, c2^0'=c2^post_4, m^0'=m^post_4, max^0'=max^post_4, n^0'=n^post_4, pi^0'=pi^post_4, pos^0'=pos^post_4, seq^0'=seq^post_4, wpos^0'=wpos^post_4, z^0'=z^post_4, [ c1^0==c1^post_4 && c2^0==c2^post_4 && m^0==m^post_4 && max^0==max^post_4 && n^0==n^post_4 && pi^0==pi^post_4 && pos^0==pos^post_4 && seq^0==seq^post_4 && wpos^0==wpos^post_4 && z^0==z^post_4 ], cost: 1

Checking for constant complexity:
   The following rule is satisfiable with cost >= 1, yielding constant complexity:
      3: l3 -> l2 : c1^0'=c1^post_4, c2^0'=c2^post_4, m^0'=m^post_4, max^0'=max^post_4, n^0'=n^post_4, pi^0'=pi^post_4, pos^0'=pos^post_4, seq^0'=seq^post_4, wpos^0'=wpos^post_4, z^0'=z^post_4, [ c1^0==c1^post_4 && c2^0==c2^post_4 && m^0==m^post_4 && max^0==max^post_4 && n^0==n^post_4 && pi^0==pi^post_4 && pos^0==pos^post_4 && seq^0==seq^post_4 && wpos^0==wpos^post_4 && z^0==z^post_4 ], cost: 1

Simplified all rules, resulting in:
   Start location: l3
      0: l0 -> l1 : c1^0'=1, c2^0'=0, pi^0'=seq^0, pos^0'=1, seq^0'=1+seq^0, wpos^0'=0, z^0'=0, [ z^0<=0 && 1-pos^0==0 && -wpos^0==0 && 1-pi^0==0 && 1<=-1+m^0 && 1+m^0<=max^0 && 1<=1+seq^0 ], cost: 1
      1: l1 -> l0 : [], cost: 1
      2: l2 -> l0 : c1^0'=0, m^0'=m^post_3, max^0'=max^post_3, n^0'=n^post_3, pi^0'=1, pos^0'=1, seq^0'=1, wpos^0'=0, z^0'=0, [ max^post_3<=n^post_3 && m^post_3<=max^post_3 && 1<=m^post_3 ], cost: 1
      3: l3 -> l2 : [], cost: 1

### Simplification by acceleration and chaining ###

Eliminated locations (on linear paths):
   Start location: l3
      5: l0 -> l0 : c1^0'=1, c2^0'=0, pi^0'=seq^0, pos^0'=1, seq^0'=1+seq^0, wpos^0'=0, z^0'=0, [ z^0<=0 && 1-pos^0==0 && -wpos^0==0 && 1-pi^0==0 && 1<=-1+m^0 && 1+m^0<=max^0 && 1<=1+seq^0 ], cost: 2
      4: l3 -> l0 : c1^0'=0, m^0'=m^post_3, max^0'=max^post_3, n^0'=n^post_3, pi^0'=1, pos^0'=1, seq^0'=1, wpos^0'=0, z^0'=0, [ max^post_3<=n^post_3 && m^post_3<=max^post_3 && 1<=m^post_3 ], cost: 2

Accelerating simple loops of location 0.
   Accelerating the following rules:
      5: l0 -> l0 : c1^0'=1, c2^0'=0, pi^0'=seq^0, pos^0'=1, seq^0'=1+seq^0, wpos^0'=0, z^0'=0, [ z^0<=0 && 1-pos^0==0 && -wpos^0==0 && 1-pi^0==0 && 1<=-1+m^0 && 1+m^0<=max^0 && 1<=1+seq^0 ], cost: 2

   Failed to prove monotonicity of the guard of rule 5.
[accelerate] Nesting with 1 inner and 1 outer candidates

Accelerated all simple loops using metering functions (where possible):
   Start location: l3
      5: l0 -> l0 : c1^0'=1, c2^0'=0, pi^0'=seq^0, pos^0'=1, seq^0'=1+seq^0, wpos^0'=0, z^0'=0, [ z^0<=0 && 1-pos^0==0 && -wpos^0==0 && 1-pi^0==0 && 1<=-1+m^0 && 1+m^0<=max^0 && 1<=1+seq^0 ], cost: 2
      4: l3 -> l0 : c1^0'=0, m^0'=m^post_3, max^0'=max^post_3, n^0'=n^post_3, pi^0'=1, pos^0'=1, seq^0'=1, wpos^0'=0, z^0'=0, [ max^post_3<=n^post_3 && m^post_3<=max^post_3 && 1<=m^post_3 ], cost: 2

Chained accelerated rules (with incoming rules):
   Start location: l3
      4: l3 -> l0 : c1^0'=0, m^0'=m^post_3, max^0'=max^post_3, n^0'=n^post_3, pi^0'=1, pos^0'=1, seq^0'=1, wpos^0'=0, z^0'=0, [ max^post_3<=n^post_3 && m^post_3<=max^post_3 && 1<=m^post_3 ], cost: 2
      6: l3 -> l0 : c1^0'=1, c2^0'=0, m^0'=m^post_3, max^0'=max^post_3, n^0'=n^post_3, pi^0'=1, pos^0'=1, seq^0'=2, wpos^0'=0, z^0'=0, [ max^post_3<=n^post_3 && 1<=-1+m^post_3 && 1+m^post_3<=max^post_3 ], cost: 4

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

### Computing asymptotic complexity ###

Fully simplified ITS problem
   Start location: l3
     <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:  [ c1^0==c1^post_4 && c2^0==c2^post_4 && m^0==m^post_4 && max^0==max^post_4 && n^0==n^post_4 && pi^0==pi^post_4 && pos^0==pos^post_4 && seq^0==seq^post_4 && wpos^0==wpos^post_4 && z^0==z^post_4 ]

WORST_CASE(Omega(1),?)