YES(?,O(n^1))

Problem:
 f(j(x,y),y) -> g(f(x,k(y)))
 f(x,h1(y,z)) -> h2(0(),x,h1(y,z))
 g(h2(x,y,h1(z,u))) -> h2(s(x),y,h1(z,u))
 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
 k(h(x)) -> h1(0(),x)
 k(h1(x,y)) -> h1(s(x),y)

Proof:
 Matrix Interpretation Processor:
  dimension: 1
  interpretation:
   [i](x0) = x0 + 2,
   
   [h](x0) = x0 + 4,
   
   [s](x0) = x0,
   
   [h2](x0, x1, x2) = x0 + x1 + x2 + 9,
   
   [0] = 2,
   
   [h1](x0, x1) = x0 + x1,
   
   [g](x0) = x0 + 8,
   
   [k](x0) = x0 + 3,
   
   [f](x0, x1) = x0 + x1 + 16,
   
   [j](x0, x1) = x0 + x1 + 24
  orientation:
   f(j(x,y),y) = x + 2y + 40 >= x + y + 27 = g(f(x,k(y)))
   
   f(x,h1(y,z)) = x + y + z + 16 >= x + y + z + 11 = h2(0(),x,h1(y,z))
   
   g(h2(x,y,h1(z,u))) = u + x + y + z + 17 >= u + x + y + z + 9 = h2(s(x),y,h1(z,u))
   
   h2(x,j(y,h1(z,u)),h1(z,u)) = 2u + x + y + 2z + 33 >= u + x + y + z + 9 = h2(s(x),y,h1(s(z),u))
   
   i(f(x,h(y))) = x + y + 22 >= y = y
   
   i(h2(s(x),y,h1(x,z))) = 2x + y + z + 11 >= z = z
   
   k(h(x)) = x + 7 >= x + 2 = h1(0(),x)
   
   k(h1(x,y)) = x + y + 3 >= x + y = h1(s(x),y)
  problem:
   
  Qed