The Runtime Complexity (innermost) of the given CpxRelTRS could be proven to be BOUNDS(n^1, INF).

(0) Obligation:

Runtime Complexity Relative TRS:
The TRS R consists of the following rules:

lt0(Nil, Cons(x', xs)) → True
lt0(Cons(x', xs'), Cons(x, xs)) → lt0(xs', xs)
g(x, Nil) → Cons(Nil, Cons(Nil, Cons(Nil, Cons(Nil, Nil))))
f(x, Nil) → Cons(Nil, Cons(Nil, Cons(Nil, Cons(Nil, Nil))))
notEmpty(Cons(x, xs)) → True
notEmpty(Nil) → False
lt0(x, Nil) → False
g(x, Cons(x', xs)) → g[Ite][False][Ite](lt0(x, Cons(Nil, Nil)), x, Cons(x', xs))
f(x, Cons(x', xs)) → f[Ite][False][Ite](lt0(x, Cons(Nil, Nil)), x, Cons(x', xs))
number4(n) → Cons(Nil, Cons(Nil, Cons(Nil, Cons(Nil, Nil))))
goal(x, y) → Cons(f(x, y), Cons(g(x, y), Nil))

The (relative) TRS S consists of the following rules:

g[Ite][False][Ite](False, Cons(x, xs), y) → g(xs, Cons(Cons(Nil, Nil), y))
g[Ite][False][Ite](True, x', Cons(x, xs)) → g(x', xs)
f[Ite][False][Ite](False, Cons(x, xs), y) → f(xs, Cons(Cons(Nil, Nil), y))
f[Ite][False][Ite](True, x', Cons(x, xs)) → f(x', xs)

Rewrite Strategy: INNERMOST

(1) DecreasingLoopProof (EQUIVALENT transformation)

The following loop(s) give(s) rise to the lower bound Ω(n¹):
The rewrite sequence
lt0(Cons(x', xs'), Cons(x, xs)) →⁺ lt0(xs', xs)
gives rise to a decreasing loop by considering the right hand sides subterm at position [].
The pumping substitution is [xs' / Cons(x', xs'), xs / Cons(x, xs)].
The result substitution is [ ].

(2) BOUNDS(n^1, INF)