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

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)) }
Obligation:
  innermost runtime complexity
Answer:
  YES(?,O(n^5))

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

 safe(f_0) = {1}, safe(a) = {}, safe(f_1) = {}, safe(g_1) = {2},
 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) = {}

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 .

Following symbols are considered recursive:

 {g_1, g_2, g_3, g_4, g_5}

The recursion depth is 5.

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;))
                                               

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