### 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)),?)