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

Strict Trs:
  { f(x, h1(y, z)) -> h2(0(), x, h1(y, z))
  , f(j(x, y), y) -> g(f(x, k(y)))
  , g(h2(x, y, h1(z, u))) -> h2(s(x), y, h1(z, u))
  , k(h1(x, y)) -> h1(s(x), y)
  , k(h(x)) -> h1(0(), x)
  , h2(x, j(y, h1(z, u)), h1(z, u)) -> h2(s(x), y, h1(s(z), u))
  , i(f(x, h(y))) -> y
  , i(h2(s(x), y, h1(x, z))) -> z }
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.
{ f_0(2, 2) -> 1
, f_1(2, 6) -> 5
, j_0(2, 2) -> 2
, g_0(2) -> 1
, g_1(5) -> 1
, g_1(5) -> 5
, k_0(2) -> 1
, k_1(2) -> 6
, h1_0(2, 2) -> 2
, h1_1(2, 2) -> 4
, h1_1(3, 2) -> 1
, h1_1(3, 2) -> 6
, h1_1(7, 2) -> 1
, h1_1(7, 2) -> 6
, h1_2(3, 2) -> 9
, h1_2(7, 2) -> 9
, h2_0(2, 2, 2) -> 1
, h2_1(3, 2, 4) -> 1
, h2_1(7, 2, 6) -> 1
, h2_1(7, 2, 6) -> 5
, h2_1(11, 2, 6) -> 5
, h2_2(8, 2, 9) -> 5
, h2_2(10, 2, 9) -> 1
, h2_2(10, 2, 9) -> 5
, 0_0() -> 2
, 0_1() -> 3
, 0_2() -> 8
, s_0(2) -> 2
, s_1(2) -> 7
, s_1(3) -> 7
, s_1(7) -> 7
, s_1(8) -> 11
, s_1(10) -> 7
, s_1(11) -> 7
, s_2(7) -> 10
, s_2(8) -> 10
, s_2(10) -> 10
, s_2(11) -> 10
, i_0(2) -> 1
, h_0(2) -> 2 }

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