WORST_CASE(Omega(1),?)

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

Initial linear ITS problem
   Start location: l4
      0: l0 -> l1 : Fnew5^0'=Fnew5^post_1, Fold6^0'=Fold6^post_1, __const_30^0'=__const_30^post_1, a^0'=a^post_1, ans8^0'=ans8^post_1, i4^0'=i4^post_1, n3^0'=n3^post_1, ret_fib9^0'=ret_fib9^post_1, temp7^0'=temp7^post_1, tmp^0'=tmp^post_1, [ 1+n3^0<=i4^0 && ans8^post_1==Fnew5^0 && ret_fib9^post_1==ans8^post_1 && tmp^post_1==ret_fib9^post_1 && Fnew5^0==Fnew5^post_1 && Fold6^0==Fold6^post_1 && __const_30^0==__const_30^post_1 && a^0==a^post_1 && i4^0==i4^post_1 && n3^0==n3^post_1 && temp7^0==temp7^post_1 ], cost: 1
      1: l0 -> l2 : Fnew5^0'=Fnew5^post_2, Fold6^0'=Fold6^post_2, __const_30^0'=__const_30^post_2, a^0'=a^post_2, ans8^0'=ans8^post_2, i4^0'=i4^post_2, n3^0'=n3^post_2, ret_fib9^0'=ret_fib9^post_2, temp7^0'=temp7^post_2, tmp^0'=tmp^post_2, [ i4^0<=n3^0 && temp7^post_2==Fnew5^0 && Fnew5^post_2==Fold6^0+Fnew5^0 && Fold6^post_2==temp7^post_2 && i4^post_2==1+i4^0 && __const_30^0==__const_30^post_2 && a^0==a^post_2 && ans8^0==ans8^post_2 && n3^0==n3^post_2 && ret_fib9^0==ret_fib9^post_2 && tmp^0==tmp^post_2 ], cost: 1
      2: l2 -> l0 : Fnew5^0'=Fnew5^post_3, Fold6^0'=Fold6^post_3, __const_30^0'=__const_30^post_3, a^0'=a^post_3, ans8^0'=ans8^post_3, i4^0'=i4^post_3, n3^0'=n3^post_3, ret_fib9^0'=ret_fib9^post_3, temp7^0'=temp7^post_3, tmp^0'=tmp^post_3, [ Fnew5^0==Fnew5^post_3 && Fold6^0==Fold6^post_3 && __const_30^0==__const_30^post_3 && a^0==a^post_3 && ans8^0==ans8^post_3 && i4^0==i4^post_3 && n3^0==n3^post_3 && ret_fib9^0==ret_fib9^post_3 && temp7^0==temp7^post_3 && tmp^0==tmp^post_3 ], cost: 1
      3: l3 -> l2 : Fnew5^0'=Fnew5^post_4, Fold6^0'=Fold6^post_4, __const_30^0'=__const_30^post_4, a^0'=a^post_4, ans8^0'=ans8^post_4, i4^0'=i4^post_4, n3^0'=n3^post_4, ret_fib9^0'=ret_fib9^post_4, temp7^0'=temp7^post_4, tmp^0'=tmp^post_4, [ a^post_4==__const_30^0 && n3^post_4==a^post_4 && Fnew5^post_4==1 && Fold6^post_4==0 && i4^post_4==2 && __const_30^0==__const_30^post_4 && ans8^0==ans8^post_4 && ret_fib9^0==ret_fib9^post_4 && temp7^0==temp7^post_4 && tmp^0==tmp^post_4 ], cost: 1
      4: l4 -> l3 : Fnew5^0'=Fnew5^post_5, Fold6^0'=Fold6^post_5, __const_30^0'=__const_30^post_5, a^0'=a^post_5, ans8^0'=ans8^post_5, i4^0'=i4^post_5, n3^0'=n3^post_5, ret_fib9^0'=ret_fib9^post_5, temp7^0'=temp7^post_5, tmp^0'=tmp^post_5, [ Fnew5^0==Fnew5^post_5 && Fold6^0==Fold6^post_5 && __const_30^0==__const_30^post_5 && a^0==a^post_5 && ans8^0==ans8^post_5 && i4^0==i4^post_5 && n3^0==n3^post_5 && ret_fib9^0==ret_fib9^post_5 && temp7^0==temp7^post_5 && tmp^0==tmp^post_5 ], cost: 1

Checking for constant complexity:
   The following rule is satisfiable with cost >= 1, yielding constant complexity:
      4: l4 -> l3 : Fnew5^0'=Fnew5^post_5, Fold6^0'=Fold6^post_5, __const_30^0'=__const_30^post_5, a^0'=a^post_5, ans8^0'=ans8^post_5, i4^0'=i4^post_5, n3^0'=n3^post_5, ret_fib9^0'=ret_fib9^post_5, temp7^0'=temp7^post_5, tmp^0'=tmp^post_5, [ Fnew5^0==Fnew5^post_5 && Fold6^0==Fold6^post_5 && __const_30^0==__const_30^post_5 && a^0==a^post_5 && ans8^0==ans8^post_5 && i4^0==i4^post_5 && n3^0==n3^post_5 && ret_fib9^0==ret_fib9^post_5 && temp7^0==temp7^post_5 && tmp^0==tmp^post_5 ], cost: 1

Removed unreachable and leaf rules:
   Start location: l4
      1: l0 -> l2 : Fnew5^0'=Fnew5^post_2, Fold6^0'=Fold6^post_2, __const_30^0'=__const_30^post_2, a^0'=a^post_2, ans8^0'=ans8^post_2, i4^0'=i4^post_2, n3^0'=n3^post_2, ret_fib9^0'=ret_fib9^post_2, temp7^0'=temp7^post_2, tmp^0'=tmp^post_2, [ i4^0<=n3^0 && temp7^post_2==Fnew5^0 && Fnew5^post_2==Fold6^0+Fnew5^0 && Fold6^post_2==temp7^post_2 && i4^post_2==1+i4^0 && __const_30^0==__const_30^post_2 && a^0==a^post_2 && ans8^0==ans8^post_2 && n3^0==n3^post_2 && ret_fib9^0==ret_fib9^post_2 && tmp^0==tmp^post_2 ], cost: 1
      2: l2 -> l0 : Fnew5^0'=Fnew5^post_3, Fold6^0'=Fold6^post_3, __const_30^0'=__const_30^post_3, a^0'=a^post_3, ans8^0'=ans8^post_3, i4^0'=i4^post_3, n3^0'=n3^post_3, ret_fib9^0'=ret_fib9^post_3, temp7^0'=temp7^post_3, tmp^0'=tmp^post_3, [ Fnew5^0==Fnew5^post_3 && Fold6^0==Fold6^post_3 && __const_30^0==__const_30^post_3 && a^0==a^post_3 && ans8^0==ans8^post_3 && i4^0==i4^post_3 && n3^0==n3^post_3 && ret_fib9^0==ret_fib9^post_3 && temp7^0==temp7^post_3 && tmp^0==tmp^post_3 ], cost: 1
      3: l3 -> l2 : Fnew5^0'=Fnew5^post_4, Fold6^0'=Fold6^post_4, __const_30^0'=__const_30^post_4, a^0'=a^post_4, ans8^0'=ans8^post_4, i4^0'=i4^post_4, n3^0'=n3^post_4, ret_fib9^0'=ret_fib9^post_4, temp7^0'=temp7^post_4, tmp^0'=tmp^post_4, [ a^post_4==__const_30^0 && n3^post_4==a^post_4 && Fnew5^post_4==1 && Fold6^post_4==0 && i4^post_4==2 && __const_30^0==__const_30^post_4 && ans8^0==ans8^post_4 && ret_fib9^0==ret_fib9^post_4 && temp7^0==temp7^post_4 && tmp^0==tmp^post_4 ], cost: 1
      4: l4 -> l3 : Fnew5^0'=Fnew5^post_5, Fold6^0'=Fold6^post_5, __const_30^0'=__const_30^post_5, a^0'=a^post_5, ans8^0'=ans8^post_5, i4^0'=i4^post_5, n3^0'=n3^post_5, ret_fib9^0'=ret_fib9^post_5, temp7^0'=temp7^post_5, tmp^0'=tmp^post_5, [ Fnew5^0==Fnew5^post_5 && Fold6^0==Fold6^post_5 && __const_30^0==__const_30^post_5 && a^0==a^post_5 && ans8^0==ans8^post_5 && i4^0==i4^post_5 && n3^0==n3^post_5 && ret_fib9^0==ret_fib9^post_5 && temp7^0==temp7^post_5 && tmp^0==tmp^post_5 ], cost: 1

Simplified all rules, resulting in:
   Start location: l4
      1: l0 -> l2 : Fnew5^0'=Fold6^0+Fnew5^0, Fold6^0'=Fnew5^0, i4^0'=1+i4^0, temp7^0'=Fnew5^0, [ i4^0<=n3^0 ], cost: 1
      2: l2 -> l0 : [], cost: 1
      3: l3 -> l2 : Fnew5^0'=1, Fold6^0'=0, a^0'=__const_30^0, i4^0'=2, n3^0'=__const_30^0, [], cost: 1
      4: l4 -> l3 : [], cost: 1

### Simplification by acceleration and chaining ###

Eliminated locations (on linear paths):
   Start location: l4
      6: l2 -> l2 : Fnew5^0'=Fold6^0+Fnew5^0, Fold6^0'=Fnew5^0, i4^0'=1+i4^0, temp7^0'=Fnew5^0, [ i4^0<=n3^0 ], cost: 2
      5: l4 -> l2 : Fnew5^0'=1, Fold6^0'=0, a^0'=__const_30^0, i4^0'=2, n3^0'=__const_30^0, [], cost: 2

Accelerating simple loops of location 2.
   Accelerating the following rules:
      6: l2 -> l2 : Fnew5^0'=Fold6^0+Fnew5^0, Fold6^0'=Fnew5^0, i4^0'=1+i4^0, temp7^0'=Fnew5^0, [ i4^0<=n3^0 ], cost: 2

   Found no closed form for 6.
[accelerate] Nesting with 0 inner and 1 outer candidates

Accelerated all simple loops using metering functions (where possible):
   Start location: l4
      6: l2 -> l2 : Fnew5^0'=Fold6^0+Fnew5^0, Fold6^0'=Fnew5^0, i4^0'=1+i4^0, temp7^0'=Fnew5^0, [ i4^0<=n3^0 ], cost: 2
      5: l4 -> l2 : Fnew5^0'=1, Fold6^0'=0, a^0'=__const_30^0, i4^0'=2, n3^0'=__const_30^0, [], cost: 2

Chained accelerated rules (with incoming rules):
   Start location: l4
      5: l4 -> l2 : Fnew5^0'=1, Fold6^0'=0, a^0'=__const_30^0, i4^0'=2, n3^0'=__const_30^0, [], cost: 2
      7: l4 -> l2 : Fnew5^0'=1, Fold6^0'=1, a^0'=__const_30^0, i4^0'=3, n3^0'=__const_30^0, temp7^0'=1, [ 2<=__const_30^0 ], cost: 4

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

### Computing asymptotic complexity ###

Fully simplified ITS problem
   Start location: l4
     <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:  [ Fnew5^0==Fnew5^post_5 && Fold6^0==Fold6^post_5 && __const_30^0==__const_30^post_5 && a^0==a^post_5 && ans8^0==ans8^post_5 && i4^0==i4^post_5 && n3^0==n3^post_5 && ret_fib9^0==ret_fib9^post_5 && temp7^0==temp7^post_5 && tmp^0==tmp^post_5 ]

WORST_CASE(Omega(1),?)