YES(?,O(n^1))

Problem:
 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)))))

Proof:
 Complexity Transformation Processor:
  strict:
   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)))))
  weak:
   
  Matrix Interpretation Processor:
   dimension: 1
   max_matrix:
    1
    interpretation:
     [s](x0) = x0 + 1,
     
     [N](x0, x1) = x0 + x1,
     
     [0] = 0,
     
     [max](x0) = x0,
     
     [L](x0) = x0
    orientation:
     max(L(x)) = x >= x = x
     
     max(N(L(0()),L(y))) = y >= y = y
     
     max(N(L(s(x)),L(s(y)))) = x + y + 2 >= x + y + 1 = s(max(N(L(x),L(y))))
     
     max(N(L(x),N(y,z))) = x + y + z >= x + y + z = max(N(L(x),L(max(N(y,z)))))
    problem:
     strict:
      max(L(x)) -> x
      max(N(L(0()),L(y))) -> y
      max(N(L(x),N(y,z))) -> max(N(L(x),L(max(N(y,z)))))
     weak:
      max(N(L(s(x)),L(s(y)))) -> s(max(N(L(x),L(y))))
    Matrix Interpretation Processor:
     dimension: 1
     max_matrix:
      1
      interpretation:
       [s](x0) = x0,
       
       [N](x0, x1) = x0 + x1,
       
       [0] = 0,
       
       [max](x0) = x0 + 1,
       
       [L](x0) = x0
      orientation:
       max(L(x)) = x + 1 >= x = x
       
       max(N(L(0()),L(y))) = y + 1 >= y = y
       
       max(N(L(x),N(y,z))) = x + y + z + 1 >= x + y + z + 2 = max(N(L(x),L(max(N(y,z)))))
       
       max(N(L(s(x)),L(s(y)))) = x + y + 1 >= x + y + 1 = s(max(N(L(x),L(y))))
      problem:
       strict:
        max(N(L(x),N(y,z))) -> max(N(L(x),L(max(N(y,z)))))
       weak:
        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))))
      Bounds Processor:
       bound: 1
       enrichment: match
       automaton:
        final states: {6,7}
        transitions:
         max1(17) -> 14,6
         max1(13) -> 14*
         N1(6,6) -> 13*
         N1(7,7) -> 13*
         N1(6,7) -> 13*
         N1(16,15) -> 17*
         N1(7,6) -> 13*
         L1(7) -> 16*
         L1(14) -> 15*
         L1(6) -> 16*
         s1(6) -> 14*
         max0(7) -> 6*
         max0(6) -> 6*
         N0(6,6) -> 6*
         N0(7,7) -> 6*
         N0(6,7) -> 6*
         N0(7,6) -> 6*
         L0(7) -> 6*
         L0(6) -> 6*
         00() -> 7*
         s0(7) -> 6*
         s0(6) -> 6*
         6 -> 14*
         7 -> 14,6
         14 -> 6*
       problem:
        strict:
         
        weak:
         max(N(L(x),N(y,z))) -> max(N(L(x),L(max(N(y,z)))))
         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))))
       Qed