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

Strict Trs:
  { f_0(x) -> a()
  , f_1(x) -> g_1(x, x)
  , g_1(s(x), y) -> b(f_0(y), g_1(x, y))
  , f_2(x) -> g_2(x, x)
  , g_2(s(x), y) -> b(f_1(y), g_2(x, y))
  , f_3(x) -> g_3(x, x)
  , g_3(s(x), y) -> b(f_2(y), g_3(x, y))
  , f_4(x) -> g_4(x, x)
  , g_4(s(x), y) -> b(f_3(y), g_4(x, y))
  , f_5(x) -> g_5(x, x)
  , g_5(s(x), y) -> b(f_4(y), g_5(x, y))
  , f_6(x) -> g_6(x, x)
  , g_6(s(x), y) -> b(f_5(y), g_6(x, y))
  , f_7(x) -> g_7(x, x)
  , g_7(s(x), y) -> b(f_6(y), g_7(x, y))
  , f_8(x) -> g_8(x, x)
  , g_8(s(x), y) -> b(f_7(y), g_8(x, y))
  , f_9(x) -> g_9(x, x)
  , g_9(s(x), y) -> b(f_8(y), g_9(x, y))
  , f_10(x) -> g_10(x, x)
  , g_10(s(x), y) -> b(f_9(y), g_10(x, y)) }
Obligation:
  innermost runtime complexity
Answer:
  YES(?,O(n^10))

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

 safe(f_0) = {1}, safe(a) = {}, safe(f_1) = {}, safe(g_1) = {},
 safe(s) = {1}, safe(b) = {1, 2}, safe(f_2) = {}, safe(g_2) = {},
 safe(f_3) = {}, safe(g_3) = {}, safe(f_4) = {}, safe(g_4) = {},
 safe(f_5) = {}, safe(g_5) = {}, safe(f_6) = {}, safe(g_6) = {},
 safe(f_7) = {}, safe(g_7) = {}, safe(f_8) = {}, safe(g_8) = {},
 safe(f_9) = {}, safe(g_9) = {}, safe(f_10) = {}, safe(g_10) = {}

and precedence

 f_1 > g_1, g_1 > f_0, f_2 > g_2, g_2 > f_1, f_3 > g_3, g_3 > f_2,
 f_4 > g_4, g_4 > f_3, f_5 > g_5, g_5 > f_4, f_6 > g_6, g_6 > f_5,
 f_7 > g_7, g_7 > f_6, f_8 > g_8, g_8 > f_7, f_9 > g_9, g_9 > f_8,
 f_10 > g_10, g_10 > f_9 .

Following symbols are considered recursive:

 {g_1, g_2, g_3, g_4, g_5, g_6, g_7, g_8, g_9, g_10}

The recursion depth is 10.

For your convenience, here are the satisfied ordering constraints:

           f_0(; x) > a()                        
                                                 
            f_1(x;) > g_1(x,  x;)                
                                                 
   g_1(s(; x),  y;) > b(; f_0(; y),  g_1(x,  y;))
                                                 
            f_2(x;) > g_2(x,  x;)                
                                                 
   g_2(s(; x),  y;) > b(; f_1(y;),  g_2(x,  y;)) 
                                                 
            f_3(x;) > g_3(x,  x;)                
                                                 
   g_3(s(; x),  y;) > b(; f_2(y;),  g_3(x,  y;)) 
                                                 
            f_4(x;) > g_4(x,  x;)                
                                                 
   g_4(s(; x),  y;) > b(; f_3(y;),  g_4(x,  y;)) 
                                                 
            f_5(x;) > g_5(x,  x;)                
                                                 
   g_5(s(; x),  y;) > b(; f_4(y;),  g_5(x,  y;)) 
                                                 
            f_6(x;) > g_6(x,  x;)                
                                                 
   g_6(s(; x),  y;) > b(; f_5(y;),  g_6(x,  y;)) 
                                                 
            f_7(x;) > g_7(x,  x;)                
                                                 
   g_7(s(; x),  y;) > b(; f_6(y;),  g_7(x,  y;)) 
                                                 
            f_8(x;) > g_8(x,  x;)                
                                                 
   g_8(s(; x),  y;) > b(; f_7(y;),  g_8(x,  y;)) 
                                                 
            f_9(x;) > g_9(x,  x;)                
                                                 
   g_9(s(; x),  y;) > b(; f_8(y;),  g_9(x,  y;)) 
                                                 
           f_10(x;) > g_10(x,  x;)               
                                                 
  g_10(s(; x),  y;) > b(; f_9(y;),  g_10(x,  y;))
                                                 

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