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:
 Complexity Transformation Processor:
  strict:
   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)
  weak:
   
  Matrix Interpretation Processor:
   dimension: 1
   max_matrix:
    1
    interpretation:
     [i](x0) = x0,
     
     [h](x0) = x0 + 1,
     
     [s](x0) = x0,
     
     [h2](x0, x1, x2) = x0 + x1 + x2,
     
     [0] = 0,
     
     [h1](x0, x1) = x0 + x1,
     
     [g](x0) = x0,
     
     [k](x0) = x0 + 1,
     
     [f](x0, x1) = x0 + x1 + 1,
     
     [j](x0, x1) = x0 + x1
    orientation:
     f(j(x,y),y) = x + 2y + 1 >= x + y + 2 = g(f(x,k(y)))
     
     f(x,h1(y,z)) = x + y + z + 1 >= x + y + z = h2(0(),x,h1(y,z))
     
     g(h2(x,y,h1(z,u))) = u + x + y + z >= u + x + y + z = h2(s(x),y,h1(z,u))
     
     h2(x,j(y,h1(z,u)),h1(z,u)) = 2u + x + y + 2z >= u + x + y + z = h2(s(x),y,h1(s(z),u))
     
     i(f(x,h(y))) = x + y + 2 >= y = y
     
     i(h2(s(x),y,h1(x,z))) = 2x + y + z >= z = z
     
     k(h(x)) = x + 2 >= x = h1(0(),x)
     
     k(h1(x,y)) = x + y + 1 >= x + y = h1(s(x),y)
    problem:
     strict:
      f(j(x,y),y) -> g(f(x,k(y)))
      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(h2(s(x),y,h1(x,z))) -> z
     weak:
      f(x,h1(y,z)) -> h2(0(),x,h1(y,z))
      i(f(x,h(y))) -> y
      k(h(x)) -> h1(0(),x)
      k(h1(x,y)) -> h1(s(x),y)
    Matrix Interpretation Processor:
     dimension: 1
     max_matrix:
      1
      interpretation:
       [i](x0) = x0,
       
       [h](x0) = x0,
       
       [s](x0) = x0,
       
       [h2](x0, x1, x2) = x0 + x1 + x2,
       
       [0] = 0,
       
       [h1](x0, x1) = x0 + x1,
       
       [g](x0) = x0,
       
       [k](x0) = x0,
       
       [f](x0, x1) = x0 + x1,
       
       [j](x0, x1) = x0 + x1 + 1
      orientation:
       f(j(x,y),y) = x + 2y + 1 >= x + y = g(f(x,k(y)))
       
       g(h2(x,y,h1(z,u))) = u + x + y + z >= u + x + y + z = h2(s(x),y,h1(z,u))
       
       h2(x,j(y,h1(z,u)),h1(z,u)) = 2u + x + y + 2z + 1 >= u + x + y + z = h2(s(x),y,h1(s(z),u))
       
       i(h2(s(x),y,h1(x,z))) = 2x + y + z >= z = z
       
       f(x,h1(y,z)) = x + y + z >= x + y + z = h2(0(),x,h1(y,z))
       
       i(f(x,h(y))) = x + y >= y = y
       
       k(h(x)) = x >= x = h1(0(),x)
       
       k(h1(x,y)) = x + y >= x + y = h1(s(x),y)
      problem:
       strict:
        g(h2(x,y,h1(z,u))) -> h2(s(x),y,h1(z,u))
        i(h2(s(x),y,h1(x,z))) -> z
       weak:
        f(j(x,y),y) -> g(f(x,k(y)))
        h2(x,j(y,h1(z,u)),h1(z,u)) -> h2(s(x),y,h1(s(z),u))
        f(x,h1(y,z)) -> h2(0(),x,h1(y,z))
        i(f(x,h(y))) -> y
        k(h(x)) -> h1(0(),x)
        k(h1(x,y)) -> h1(s(x),y)
      Matrix Interpretation Processor:
       dimension: 1
       max_matrix:
        1
        interpretation:
         [i](x0) = x0,
         
         [h](x0) = x0,
         
         [s](x0) = x0 + 1,
         
         [h2](x0, x1, x2) = x0 + x1 + x2,
         
         [0] = 0,
         
         [h1](x0, x1) = x0 + x1 + 1,
         
         [g](x0) = x0,
         
         [k](x0) = x0 + 1,
         
         [f](x0, x1) = x0 + x1,
         
         [j](x0, x1) = x0 + x1 + 1
        orientation:
         g(h2(x,y,h1(z,u))) = u + x + y + z + 1 >= u + x + y + z + 2 = h2(s(x),y,h1(z,u))
         
         i(h2(s(x),y,h1(x,z))) = 2x + y + z + 2 >= z = z
         
         f(j(x,y),y) = x + 2y + 1 >= x + y + 1 = g(f(x,k(y)))
         
         h2(x,j(y,h1(z,u)),h1(z,u)) = 2u + x + y + 2z + 3 >= u + x + y + z + 3 = h2(s(x),y,h1(s(z),u))
         
         f(x,h1(y,z)) = x + y + z + 1 >= x + y + z + 1 = h2(0(),x,h1(y,z))
         
         i(f(x,h(y))) = x + y >= y = y
         
         k(h(x)) = x + 1 >= x + 1 = h1(0(),x)
         
         k(h1(x,y)) = x + y + 2 >= x + y + 2 = h1(s(x),y)
        problem:
         strict:
          g(h2(x,y,h1(z,u))) -> h2(s(x),y,h1(z,u))
         weak:
          i(h2(s(x),y,h1(x,z))) -> z
          f(j(x,y),y) -> g(f(x,k(y)))
          h2(x,j(y,h1(z,u)),h1(z,u)) -> h2(s(x),y,h1(s(z),u))
          f(x,h1(y,z)) -> h2(0(),x,h1(y,z))
          i(f(x,h(y))) -> y
          k(h(x)) -> h1(0(),x)
          k(h1(x,y)) -> h1(s(x),y)
        Matrix Interpretation Processor:
         dimension: 1
         max_matrix:
          1
          interpretation:
           [i](x0) = x0,
           
           [h](x0) = x0 + 1,
           
           [s](x0) = x0,
           
           [h2](x0, x1, x2) = x0 + x1 + x2,
           
           [0] = 0,
           
           [h1](x0, x1) = x0 + x1,
           
           [g](x0) = x0 + 1,
           
           [k](x0) = x0,
           
           [f](x0, x1) = x0 + x1,
           
           [j](x0, x1) = x0 + x1 + 1
          orientation:
           g(h2(x,y,h1(z,u))) = u + x + y + z + 1 >= u + x + y + z = h2(s(x),y,h1(z,u))
           
           i(h2(s(x),y,h1(x,z))) = 2x + y + z >= z = z
           
           f(j(x,y),y) = x + 2y + 1 >= x + y + 1 = g(f(x,k(y)))
           
           h2(x,j(y,h1(z,u)),h1(z,u)) = 2u + x + y + 2z + 1 >= u + x + y + z = h2(s(x),y,h1(s(z),u))
           
           f(x,h1(y,z)) = x + y + z >= x + y + z = h2(0(),x,h1(y,z))
           
           i(f(x,h(y))) = x + y + 1 >= y = y
           
           k(h(x)) = x + 1 >= x = h1(0(),x)
           
           k(h1(x,y)) = x + y >= x + y = h1(s(x),y)
          problem:
           strict:
            
           weak:
            g(h2(x,y,h1(z,u))) -> h2(s(x),y,h1(z,u))
            i(h2(s(x),y,h1(x,z))) -> z
            f(j(x,y),y) -> g(f(x,k(y)))
            h2(x,j(y,h1(z,u)),h1(z,u)) -> h2(s(x),y,h1(s(z),u))
            f(x,h1(y,z)) -> h2(0(),x,h1(y,z))
            i(f(x,h(y))) -> y
            k(h(x)) -> h1(0(),x)
            k(h1(x,y)) -> h1(s(x),y)
          Qed