* Step 1: MI WORST_CASE(?,O(n^1))
+ Considered Problem:
- Strict TRS:
g(f(x),y) -> f(h(x,y))
h(x,y) -> g(x,f(y))
- Signature:
{g/2,h/2} / {f/1}
- Obligation:
innermost runtime complexity wrt. defined symbols {g,h} and constructors {f}
+ Applied Processor:
MI {miKind = MaximalMatrix (UpperTriangular (Multiplicity Nothing)), miDimension = 1, miUArgs = UArgs, miURules = URules, miSelector = Just any strict-rules}
+ Details:
We apply a matrix interpretation of kind MaximalMatrix (UpperTriangular (Multiplicity Nothing)):
The following argument positions are considered usable:
uargs(f) = {1}
Following symbols are considered usable:
{g,h}
TcT has computed the following interpretation:
p(f) = [1] x_1 + [12]
p(g) = [2] x_1 + [0]
p(h) = [2] x_1 + [1]
Following rules are strictly oriented:
g(f(x),y) = [2] x + [24]
> [2] x + [13]
= f(h(x,y))
h(x,y) = [2] x + [1]
> [2] x + [0]
= g(x,f(y))
Following rules are (at-least) weakly oriented:
* Step 2: EmptyProcessor WORST_CASE(?,O(1))
+ Considered Problem:
- Weak TRS:
g(f(x),y) -> f(h(x,y))
h(x,y) -> g(x,f(y))
- Signature:
{g/2,h/2} / {f/1}
- Obligation:
innermost runtime complexity wrt. defined symbols {g,h} and constructors {f}
+ Applied Processor:
EmptyProcessor
+ Details:
The problem is already closed. The intended complexity is O(1).
WORST_CASE(?,O(n^1))