We are left with following problem, upon which TcT provides the
certificate YES(?,O(n^1)).

Strict Trs:
  { eq0(S(x'), S(x)) -> eq0(x', x)
  , eq0(S(x), 0()) -> 0()
  , eq0(0(), S(x)) -> 0()
  , eq0(0(), 0()) -> S(0()) }
Obligation:
  innermost runtime complexity
Answer:
  YES(?,O(n^1))

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

 safe(eq0) = {2}, safe(S) = {1}, safe(0) = {}

and precedence

 empty .

Following symbols are considered recursive:

 {eq0}

The recursion depth is 1.

For your convenience, here are the satisfied ordering constraints:

  eq0(S(; x'); S(; x)) > eq0(x'; x)
                                   
      eq0(S(; x); 0()) > 0()       
                                   
      eq0(0(); S(; x)) > 0()       
                                   
         eq0(0(); 0()) > S(; 0())  
                                   

Hurray, we answered YES(?,O(n^1))