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

Initial linear ITS problem
   Start location: f0
      0: f0 -> f : [ x>y^2 ], cost: y

Added constraints to the guards to ensure costs are nonnegative:
   Start location: f0
      0: f0 -> f : [ x>y^2 && y>=0 ], cost: y

Checking for constant complexity:
   The following rule is satisfiable with cost >= 1, yielding constant complexity:
      0: f0 -> f : [ x>y^2 && y>=0 ], cost: y

### Simplification by acceleration and chaining ###

### Computing asymptotic complexity ###

Fully simplified ITS problem
   Start location: f0
      0: f0 -> f : [ x>y^2 && y>=0 ], cost: y

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

      applying transformation rule (C) using substitution {x==1+y^2}
      resulting limit problem:
      1 (+/+!), 1+y (+/+!), y (+) [not solved]

      applying transformation rule (B), deleting 1 (+/+!)
      resulting limit problem:
      1+y (+/+!), y (+) [not solved]

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

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

   Solution:
      x / 1+n^2
      y / n
   Resulting cost n has complexity: Poly(n^(1/2))

Found new complexity Poly(n^(1/2)).

Obtained the following overall complexity (w.r.t. the length of the input n):
   Complexity:  Poly(n^(1/2))
   Cpx degree:  0.5
   Solved cost: n
   Rule cost:   y
   Rule guard:  [ x>y^2 && y>=0 ]

WORST_CASE(Omega(n^(1/2)),?)