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

(0) Obligation:

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

average(x, y) → if(ge(x, y), x, y)
if(true, x, y) → averIter(y, x, y)
if(false, x, y) → averIter(x, y, x)
averIter(x, y, z) → ifIter(ge(x, y), x, y, z)
ifIter(true, x, y, z) → z
ifIter(false, x, y, z) → averIter(plus(x, s(s(s(0)))), plus(y, s(0)), plus(z, s(0)))
append(nil, y) → y
append(cons(n, x), y) → cons(n, app(x, y))
low(n, nil) → nil
low(n, cons(m, x)) → if_low(ge(m, n), n, cons(m, x))
if_low(false, n, cons(m, x)) → cons(m, low(n, x))
if_low(true, n, cons(m, x)) → low(n, x)
high(n, nil) → nil
high(n, cons(m, x)) → if_high(ge(m, n), n, cons(m, x))
if_high(false, n, cons(m, x)) → high(n, x)
if_high(true, n, cons(m, x)) → cons(average(m, m), high(n, x))
quicksort(x) → ifquick(isempty(x), x)
ifquick(true, x) → nil
ifquick(false, x) → append(quicksort(low(head(x), tail(x))), cons(tail(x), quicksort(high(head(x), tail(x)))))
plus(0, y) → y
plus(s(x), y) → s(plus(x, y))
isempty(nil) → true
isempty(cons(n, x)) → false
head(nil) → error
head(cons(n, x)) → n
tail(nil) → nil
tail(cons(n, x)) → x
ge(x, 0) → true
ge(0, s(y)) → false
ge(s(x), s(y)) → ge(x, y)
a → b
a → c

Rewrite Strategy: FULL

(1) DecreasingLoopProof (EQUIVALENT transformation)

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

(2) BOUNDS(n^1, INF)