YES(?,O(n^2))

Problem:
 f(a,empty()) -> g(a,empty())
 f(a,cons(x,k)) -> f(cons(x,a),k)
 g(empty(),d) -> d
 g(cons(x,k),d) -> g(k,cons(x,d))

Proof:
 Complexity Transformation Processor:
  strict:
   f(a,empty()) -> g(a,empty())
   f(a,cons(x,k)) -> f(cons(x,a),k)
   g(empty(),d) -> d
   g(cons(x,k),d) -> g(k,cons(x,d))
  weak:
   
  Matrix Interpretation Processor:
   dimension: 1
   max_matrix:
    1
    interpretation:
     [cons](x0, x1) = x0 + x1,
     
     [g](x0, x1) = x0 + x1,
     
     [f](x0, x1) = x0 + x1,
     
     [empty] = 1
    orientation:
     f(a,empty()) = a + 1 >= a + 1 = g(a,empty())
     
     f(a,cons(x,k)) = a + k + x >= a + k + x = f(cons(x,a),k)
     
     g(empty(),d) = d + 1 >= d = d
     
     g(cons(x,k),d) = d + k + x >= d + k + x = g(k,cons(x,d))
    problem:
     strict:
      f(a,empty()) -> g(a,empty())
      f(a,cons(x,k)) -> f(cons(x,a),k)
      g(cons(x,k),d) -> g(k,cons(x,d))
     weak:
      g(empty(),d) -> d
    Matrix Interpretation Processor:
     dimension: 1
     max_matrix:
      1
      interpretation:
       [cons](x0, x1) = x0 + x1,
       
       [g](x0, x1) = x0 + x1,
       
       [f](x0, x1) = x0 + x1 + 1,
       
       [empty] = 0
      orientation:
       f(a,empty()) = a + 1 >= a = g(a,empty())
       
       f(a,cons(x,k)) = a + k + x + 1 >= a + k + x + 1 = f(cons(x,a),k)
       
       g(cons(x,k),d) = d + k + x >= d + k + x = g(k,cons(x,d))
       
       g(empty(),d) = d >= d = d
      problem:
       strict:
        f(a,cons(x,k)) -> f(cons(x,a),k)
        g(cons(x,k),d) -> g(k,cons(x,d))
       weak:
        f(a,empty()) -> g(a,empty())
        g(empty(),d) -> d
      Matrix Interpretation Processor:
       dimension: 2
       max_matrix:
        [1 1]
        [0 1]
        interpretation:
                          [1 0]          [0]
         [cons](x0, x1) = [0 0]x0 + x1 + [1],
         
                       [1 1]       
         [g](x0, x1) = [0 1]x0 + x1,
         
                       [1 1]     [1 1]     [1]
         [f](x0, x1) = [0 1]x0 + [0 1]x1 + [0],
         
                   [0]
         [empty] = [1]
        orientation:
                          [1 1]    [1 1]    [1 0]    [2]    [1 1]    [1 1]    [1 0]    [2]                 
         f(a,cons(x,k)) = [0 1]a + [0 1]k + [0 0]x + [1] >= [0 1]a + [0 1]k + [0 0]x + [1] = f(cons(x,a),k)
         
                              [1 1]    [1 0]    [1]        [1 1]    [1 0]    [0]                 
         g(cons(x,k),d) = d + [0 1]k + [0 0]x + [1] >= d + [0 1]k + [0 0]x + [1] = g(k,cons(x,d))
         
                        [1 1]    [2]    [1 1]    [0]               
         f(a,empty()) = [0 1]a + [1] >= [0 1]a + [1] = g(a,empty())
         
                            [1]         
         g(empty(),d) = d + [1] >= d = d
        problem:
         strict:
          f(a,cons(x,k)) -> f(cons(x,a),k)
         weak:
          g(cons(x,k),d) -> g(k,cons(x,d))
          f(a,empty()) -> g(a,empty())
          g(empty(),d) -> d
        Matrix Interpretation Processor:
         dimension: 2
         max_matrix:
          [1 1]
          [0 1]
          interpretation:
                            [1 0]          [0]
           [cons](x0, x1) = [0 0]x0 + x1 + [1],
           
                                
           [g](x0, x1) = x0 + x1,
           
                              [1 1]  
           [f](x0, x1) = x0 + [0 1]x1,
           
                     [0]
           [empty] = [0]
          orientation:
                                [1 1]    [1 0]    [1]        [1 1]    [1 0]    [0]                 
           f(a,cons(x,k)) = a + [0 1]k + [0 0]x + [1] >= a + [0 1]k + [0 0]x + [1] = f(cons(x,a),k)
           
                                    [1 0]    [0]            [1 0]    [0]                 
           g(cons(x,k),d) = d + k + [0 0]x + [1] >= d + k + [0 0]x + [1] = g(k,cons(x,d))
           
                                               
           f(a,empty()) = a >= a = g(a,empty())
           
                                    
           g(empty(),d) = d >= d = d
          problem:
           strict:
            
           weak:
            f(a,cons(x,k)) -> f(cons(x,a),k)
            g(cons(x,k),d) -> g(k,cons(x,d))
            f(a,empty()) -> g(a,empty())
            g(empty(),d) -> d
          Qed