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

Strict Trs:
  { g(x, s(y)) -> g(f(x, y), 0())
  , g(0(), f(x, x)) -> x
  , g(f(x, y), 0()) -> f(g(x, 0()), g(y, 0()))
  , g(s(x), y) -> g(f(x, y), 0()) }
Obligation:
  runtime complexity
Answer:
  YES(?,O(n^1))

The input is overlay and right-linear. Switching to innermost
rewriting.

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

Strict Trs:
  { g(x, s(y)) -> g(f(x, y), 0())
  , g(0(), f(x, x)) -> x
  , g(f(x, y), 0()) -> f(g(x, 0()), g(y, 0()))
  , g(s(x), y) -> g(f(x, y), 0()) }
Obligation:
  innermost runtime complexity
Answer:
  YES(?,O(n^1))

The problem is match-bounded by 2. The enriched problem is
compatible with the following automaton.
{ g_0(2, 2) -> 1
, g_1(2, 4) -> 5
, g_1(2, 4) -> 6
, g_1(3, 4) -> 1
, g_1(4, 4) -> 6
, g_1(11, 4) -> 7
, g_1(12, 4) -> 8
, g_2(2, 9) -> 7
, g_2(2, 10) -> 8
, g_2(4, 10) -> 13
, g_2(9, 10) -> 13
, g_2(10, 10) -> 13
, 0_0() -> 1
, 0_0() -> 2
, 0_1() -> 4
, 0_2() -> 9
, 0_2() -> 10
, f_0(2, 2) -> 1
, f_0(2, 2) -> 2
, f_1(2, 2) -> 3
, f_1(2, 4) -> 1
, f_1(2, 4) -> 2
, f_1(2, 9) -> 11
, f_1(2, 10) -> 12
, f_1(5, 6) -> 1
, f_1(6, 6) -> 5
, f_1(6, 6) -> 6
, f_1(6, 6) -> 7
, f_1(6, 6) -> 8
, f_2(7, 8) -> 1
, f_2(8, 13) -> 5
, f_2(8, 13) -> 6
, f_2(8, 13) -> 7
, f_2(8, 13) -> 8
, s_0(2) -> 1
, s_0(2) -> 2 }

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