The Runtime Complexity (innermost) 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:

empty(nil) → true
empty(cons(x, l)) → false
head(cons(x, l)) → x
tail(nil) → nil
tail(cons(x, l)) → l
rev(nil) → nil
rev(cons(x, l)) → cons(rev1(x, l), rev2(x, l))
last(x, l) → if(empty(l), x, l)
if(true, x, l) → x
if(false, x, l) → last(head(l), tail(l))
rev2(x, nil) → nil
rev2(x, cons(y, l)) → rev(cons(x, rev2(y, l)))

Rewrite Strategy: INNERMOST

(1) DecreasingLoopProof (EQUIVALENT transformation)

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

(2) BOUNDS(n^1, INF)