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

(0) Obligation:

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

max(L(x)) → x
max(N(L(0), L(y))) → y
max(N(L(s(x)), L(s(y)))) → s(max(N(L(x), L(y))))
max(N(L(x), N(y, z))) → max(N(L(x), L(max(N(y, z)))))

Rewrite Strategy: INNERMOST

(1) CpxTrsMatchBoundsTAProof (EQUIVALENT transformation)

A linear upper bound on the runtime complexity of the TRS R could be shown with a Match-Bound[TAB_LEFTLINEAR,TAB_NONLEFTLINEAR] (for contructor-based start-terms) of 1.

The compatible tree automaton used to show the Match-Boundedness (for constructor-based start-terms) is represented by:
final states : [1]
transitions:
L0(0) → 0
N0(0, 0) → 0
00() → 0
s0(0) → 0
max0(0) → 1
L1(0) → 4
L1(0) → 5
N1(4, 5) → 3
max1(3) → 2
s1(2) → 1
N1(0, 0) → 8
max1(8) → 7
L1(7) → 6
N1(4, 6) → 3
max1(3) → 1
s1(2) → 7
max1(3) → 7
L1(2) → 5
0 → 1
0 → 7
0 → 2
7 → 1
7 → 2
2 → 1
2 → 7

(2) BOUNDS(1, n^1)