We are left with following problem, upon which TcT provides the
certificate YES(?,POLY).

Strict Trs:
  { f(s(x1), x2, x3, x4, x5) -> f(x1, x2, x3, x4, x5)
  , f(0(), s(x2), x3, x4, x5) -> f(x2, x2, x3, x4, x5)
  , f(0(), 0(), s(x3), x4, x5) -> f(x3, x3, x3, x4, x5)
  , f(0(), 0(), 0(), s(x4), x5) -> f(x4, x4, x4, x4, x5)
  , f(0(), 0(), 0(), 0(), s(x5)) -> f(x5, x5, x5, x5, x5)
  , f(0(), 0(), 0(), 0(), 0()) -> 0() }
Obligation:
  innermost runtime complexity
Answer:
  YES(?,POLY)

The input was oriented with the instance of 'Polynomial Path Order
(PS)' as induced by the safe mapping

 safe(f) = {}, safe(s) = {1}, safe(0) = {}

and precedence

 empty .

Following symbols are considered recursive:

 {f}

The recursion depth is 1.

For your convenience, here are the satisfied ordering constraints:

      f(s(; x1),  x2,  x3,  x4,  x5;) > f(x1,  x2,  x3,  x4,  x5;)
                                                                  
     f(0(),  s(; x2),  x3,  x4,  x5;) > f(x2,  x2,  x3,  x4,  x5;)
                                                                  
    f(0(),  0(),  s(; x3),  x4,  x5;) > f(x3,  x3,  x3,  x4,  x5;)
                                                                  
   f(0(),  0(),  0(),  s(; x4),  x5;) > f(x4,  x4,  x4,  x4,  x5;)
                                                                  
  f(0(),  0(),  0(),  0(),  s(; x5);) > f(x5,  x5,  x5,  x5,  x5;)
                                                                  
      f(0(),  0(),  0(),  0(),  0();) > 0()                       
                                                                  

Hurray, we answered YES(?,POLY)