YES(?,O(n^3))

Problem:
 f(nil()) -> nil()
 f(.(nil(),y)) -> .(nil(),f(y))
 f(.(.(x,y),z)) -> f(.(x,.(y,z)))
 g(nil()) -> nil()
 g(.(x,nil())) -> .(g(x),nil())
 g(.(x,.(y,z))) -> g(.(.(x,y),z))

Proof:
 Complexity Transformation Processor:
  strict:
   f(nil()) -> nil()
   f(.(nil(),y)) -> .(nil(),f(y))
   f(.(.(x,y),z)) -> f(.(x,.(y,z)))
   g(nil()) -> nil()
   g(.(x,nil())) -> .(g(x),nil())
   g(.(x,.(y,z))) -> g(.(.(x,y),z))
  weak:
   
  Matrix Interpretation Processor:
   dimension: 1
   max_matrix:
    1
    interpretation:
     [g](x0) = x0,
     
     [.](x0, x1) = x0 + x1,
     
     [f](x0) = x0 + 1,
     
     [nil] = 0
    orientation:
     f(nil()) = 1 >= 0 = nil()
     
     f(.(nil(),y)) = y + 1 >= y + 1 = .(nil(),f(y))
     
     f(.(.(x,y),z)) = x + y + z + 1 >= x + y + z + 1 = f(.(x,.(y,z)))
     
     g(nil()) = 0 >= 0 = nil()
     
     g(.(x,nil())) = x >= x = .(g(x),nil())
     
     g(.(x,.(y,z))) = x + y + z >= x + y + z = g(.(.(x,y),z))
    problem:
     strict:
      f(.(nil(),y)) -> .(nil(),f(y))
      f(.(.(x,y),z)) -> f(.(x,.(y,z)))
      g(nil()) -> nil()
      g(.(x,nil())) -> .(g(x),nil())
      g(.(x,.(y,z))) -> g(.(.(x,y),z))
     weak:
      f(nil()) -> nil()
    Matrix Interpretation Processor:
     dimension: 1
     max_matrix:
      1
      interpretation:
       [g](x0) = x0 + 1,
       
       [.](x0, x1) = x0 + x1,
       
       [f](x0) = x0,
       
       [nil] = 0
      orientation:
       f(.(nil(),y)) = y >= y = .(nil(),f(y))
       
       f(.(.(x,y),z)) = x + y + z >= x + y + z = f(.(x,.(y,z)))
       
       g(nil()) = 1 >= 0 = nil()
       
       g(.(x,nil())) = x + 1 >= x + 1 = .(g(x),nil())
       
       g(.(x,.(y,z))) = x + y + z + 1 >= x + y + z + 1 = g(.(.(x,y),z))
       
       f(nil()) = 0 >= 0 = nil()
      problem:
       strict:
        f(.(nil(),y)) -> .(nil(),f(y))
        f(.(.(x,y),z)) -> f(.(x,.(y,z)))
        g(.(x,nil())) -> .(g(x),nil())
        g(.(x,.(y,z))) -> g(.(.(x,y),z))
       weak:
        g(nil()) -> nil()
        f(nil()) -> nil()
      Matrix Interpretation Processor:
       dimension: 2
       max_matrix:
        [1 1]
        [0 1]
        interpretation:
                   [1 1]     [0]
         [g](x0) = [0 1]x0 + [1],
         
                                 [0]
         [.](x0, x1) = x0 + x1 + [1],
         
                     
         [f](x0) = x0,
         
                 [0]
         [nil] = [1]
        orientation:
                             [0]        [0]                
         f(.(nil(),y)) = y + [2] >= y + [2] = .(nil(),f(y))
         
                                      [0]                [0]                 
         f(.(.(x,y),z)) = x + y + z + [2] >= x + y + z + [2] = f(.(x,.(y,z)))
         
                         [1 1]    [2]    [1 1]    [0]                
         g(.(x,nil())) = [0 1]x + [3] >= [0 1]x + [3] = .(g(x),nil())
         
                          [1 1]    [1 1]    [1 1]    [2]    [1 1]    [1 1]    [1 1]    [2]                 
         g(.(x,.(y,z))) = [0 1]x + [0 1]y + [0 1]z + [3] >= [0 1]x + [0 1]y + [0 1]z + [3] = g(.(.(x,y),z))
         
                    [1]    [0]        
         g(nil()) = [2] >= [1] = nil()
         
                    [0]    [0]        
         f(nil()) = [1] >= [1] = nil()
        problem:
         strict:
          f(.(nil(),y)) -> .(nil(),f(y))
          f(.(.(x,y),z)) -> f(.(x,.(y,z)))
          g(.(x,.(y,z))) -> g(.(.(x,y),z))
         weak:
          g(.(x,nil())) -> .(g(x),nil())
          g(nil()) -> nil()
          f(nil()) -> nil()
        Matrix Interpretation Processor:
         dimension: 2
         max_matrix:
          [1 1]
          [0 1]
          interpretation:
                          [1]
           [g](x0) = x0 + [0],
           
                                
           [.](x0, x1) = x0 + x1,
           
                     [1 1]  
           [f](x0) = [0 1]x0,
           
                   [0]
           [nil] = [1]
          orientation:
                           [1 1]    [1]    [1 1]    [0]                
           f(.(nil(),y)) = [0 1]y + [1] >= [0 1]y + [1] = .(nil(),f(y))
           
                            [1 1]    [1 1]    [1 1]     [1 1]    [1 1]    [1 1]                  
           f(.(.(x,y),z)) = [0 1]x + [0 1]y + [0 1]z >= [0 1]x + [0 1]y + [0 1]z = f(.(x,.(y,z)))
           
                                        [1]                [1]                 
           g(.(x,.(y,z))) = x + y + z + [0] >= x + y + z + [0] = g(.(.(x,y),z))
           
                               [1]        [1]                
           g(.(x,nil())) = x + [1] >= x + [1] = .(g(x),nil())
           
                      [1]    [0]        
           g(nil()) = [1] >= [1] = nil()
           
                      [1]    [0]        
           f(nil()) = [1] >= [1] = nil()
          problem:
           strict:
            f(.(.(x,y),z)) -> f(.(x,.(y,z)))
            g(.(x,.(y,z))) -> g(.(.(x,y),z))
           weak:
            f(.(nil(),y)) -> .(nil(),f(y))
            g(.(x,nil())) -> .(g(x),nil())
            g(nil()) -> nil()
            f(nil()) -> nil()
          Matrix Interpretation Processor:
           dimension: 3
           max_matrix:
            [1 1 0]
            [0 1 1]
            [0 0 1]
            interpretation:
                       [1 1 0]     [1]
             [g](x0) = [0 0 0]x0 + [0]
                       [0 0 1]     [0],
             
                                [1 0 0]     [0]
             [.](x0, x1) = x0 + [0 0 1]x1 + [0]
                                [0 0 1]     [1],
             
                       [1 0 0]     [0]
             [f](x0) = [0 0 1]x0 + [1]
                       [0 0 1]     [0],
             
                     [1]
             [nil] = [0]
                     [0]
            orientation:
                              [1 0 0]    [1 0 0]    [1 0 0]    [0]    [1 0 0]    [1 0 0]    [1 0 0]    [0]                 
             f(.(.(x,y),z)) = [0 0 1]x + [0 0 1]y + [0 0 1]z + [3] >= [0 0 1]x + [0 0 1]y + [0 0 1]z + [3] = f(.(x,.(y,z)))
                              [0 0 1]    [0 0 1]    [0 0 1]    [2]    [0 0 1]    [0 0 1]    [0 0 1]    [2]                 
             
                              [1 1 0]    [1 0 1]    [1 0 1]    [2]    [1 1 0]    [1 0 1]    [1 0 1]    [1]                 
             g(.(x,.(y,z))) = [0 0 0]x + [0 0 0]y + [0 0 0]z + [0] >= [0 0 0]x + [0 0 0]y + [0 0 0]z + [0] = g(.(.(x,y),z))
                              [0 0 1]    [0 0 1]    [0 0 1]    [2]    [0 0 1]    [0 0 1]    [0 0 1]    [2]                 
             
                             [1 0 0]    [1]    [1 0 0]    [1]                
             f(.(nil(),y)) = [0 0 1]y + [2] >= [0 0 1]y + [0] = .(nil(),f(y))
                             [0 0 1]    [1]    [0 0 1]    [1]                
             
                             [1 1 0]    [2]    [1 1 0]    [2]                
             g(.(x,nil())) = [0 0 0]x + [0] >= [0 0 0]x + [0] = .(g(x),nil())
                             [0 0 1]    [1]    [0 0 1]    [1]                
             
                        [2]    [1]        
             g(nil()) = [0] >= [0] = nil()
                        [0]    [0]        
             
                        [1]    [1]        
             f(nil()) = [1] >= [0] = nil()
                        [0]    [0]        
            problem:
             strict:
              f(.(.(x,y),z)) -> f(.(x,.(y,z)))
             weak:
              g(.(x,.(y,z))) -> g(.(.(x,y),z))
              f(.(nil(),y)) -> .(nil(),f(y))
              g(.(x,nil())) -> .(g(x),nil())
              g(nil()) -> nil()
              f(nil()) -> nil()
            Matrix Interpretation Processor:
             dimension: 3
             max_matrix:
              [1 1 0]
              [0 1 1]
              [0 0 1]
              interpretation:
                         [1 1 0]     [0]
               [g](x0) = [0 0 0]x0 + [1]
                         [0 0 1]     [0],
               
                             [1 1 0]          [0]
               [.](x0, x1) = [0 0 0]x0 + x1 + [1]
                             [0 0 1]          [0],
               
                         [1 0 0]     [0]
               [f](x0) = [0 0 1]x0 + [1]
                         [0 0 1]     [0],
               
                       [0]
               [nil] = [0]
                       [1]
              orientation:
                                [1 1 0]    [1 1 0]    [1 0 0]    [1]    [1 1 0]    [1 1 0]    [1 0 0]    [0]                 
               f(.(.(x,y),z)) = [0 0 1]x + [0 0 1]y + [0 0 1]z + [1] >= [0 0 1]x + [0 0 1]y + [0 0 1]z + [1] = f(.(x,.(y,z)))
                                [0 0 1]    [0 0 1]    [0 0 1]    [0]    [0 0 1]    [0 0 1]    [0 0 1]    [0]                 
               
                                [1 1 0]    [1 1 0]    [1 1 0]    [2]    [1 1 0]    [1 1 0]    [1 1 0]    [2]                 
               g(.(x,.(y,z))) = [0 0 0]x + [0 0 0]y + [0 0 0]z + [1] >= [0 0 0]x + [0 0 0]y + [0 0 0]z + [1] = g(.(.(x,y),z))
                                [0 0 1]    [0 0 1]    [0 0 1]    [0]    [0 0 1]    [0 0 1]    [0 0 1]    [0]                 
               
                               [1 0 0]    [0]    [1 0 0]    [0]                
               f(.(nil(),y)) = [0 0 1]y + [2] >= [0 0 1]y + [2] = .(nil(),f(y))
                               [0 0 1]    [1]    [0 0 1]    [1]                
               
                               [1 1 0]    [1]    [1 1 0]    [1]                
               g(.(x,nil())) = [0 0 0]x + [1] >= [0 0 0]x + [1] = .(g(x),nil())
                               [0 0 1]    [1]    [0 0 1]    [1]                
               
                          [0]    [0]        
               g(nil()) = [1] >= [0] = nil()
                          [1]    [1]        
               
                          [0]    [0]        
               f(nil()) = [2] >= [0] = nil()
                          [1]    [1]        
              problem:
               strict:
                
               weak:
                f(.(.(x,y),z)) -> f(.(x,.(y,z)))
                g(.(x,.(y,z))) -> g(.(.(x,y),z))
                f(.(nil(),y)) -> .(nil(),f(y))
                g(.(x,nil())) -> .(g(x),nil())
                g(nil()) -> nil()
                f(nil()) -> nil()
              Qed