YES(?,O(n^2))

Problem:
 merge(x,nil()) -> x
 merge(nil(),y) -> y
 merge(++(x,y),++(u(),v())) -> ++(x,merge(y,++(u(),v())))
 merge(++(x,y),++(u(),v())) -> ++(u(),merge(++(x,y),v()))

Proof:
 Complexity Transformation Processor:
  strict:
   merge(x,nil()) -> x
   merge(nil(),y) -> y
   merge(++(x,y),++(u(),v())) -> ++(x,merge(y,++(u(),v())))
   merge(++(x,y),++(u(),v())) -> ++(u(),merge(++(x,y),v()))
  weak:
   
  Matrix Interpretation Processor:
   dimension: 1
   max_matrix:
    1
    interpretation:
     [v] = 0,
     
     [u] = 1,
     
     [++](x0, x1) = x0 + x1,
     
     [merge](x0, x1) = x0 + x1,
     
     [nil] = 1
    orientation:
     merge(x,nil()) = x + 1 >= x = x
     
     merge(nil(),y) = y + 1 >= y = y
     
     merge(++(x,y),++(u(),v())) = x + y + 1 >= x + y + 1 = ++(x,merge(y,++(u(),v())))
     
     merge(++(x,y),++(u(),v())) = x + y + 1 >= x + y + 1 = ++(u(),merge(++(x,y),v()))
    problem:
     strict:
      merge(++(x,y),++(u(),v())) -> ++(x,merge(y,++(u(),v())))
      merge(++(x,y),++(u(),v())) -> ++(u(),merge(++(x,y),v()))
     weak:
      merge(x,nil()) -> x
      merge(nil(),y) -> y
    Bounds Processor:
     bound: 2
     enrichment: match
     automaton:
      final states: {7,6}
      transitions:
       ++1(6,6) -> 21*
       ++1(7,7) -> 21*
       ++1(23,20) -> 26*
       ++1(23,22) -> 31,6
       ++1(6,7) -> 21*
       ++1(7,6) -> 21*
       ++1(6,31) -> 31,6
       merge1(22,26) -> 22*
       merge1(34,6) -> 34*
       merge1(31,6) -> 31*
       merge1(6,6) -> 31*
       merge1(31,20) -> 22*
       merge1(21,20) -> 22*
       merge1(6,20) -> 22*
       u1() -> 23*
       v1() -> 20*
       ++2(6,31) -> 33*
       ++2(23,22) -> 33*
       ++2(35,32) -> 40*
       ++2(35,34) -> 31*
       merge2(34,40) -> 34*
       merge2(31,32) -> 34*
       merge2(33,32) -> 34*
       merge0(6,6) -> 6*
       merge0(7,7) -> 6*
       merge0(6,7) -> 6*
       merge0(7,6) -> 6*
       u2() -> 35*
       ++0(6,6) -> 6*
       ++0(7,7) -> 6*
       ++0(6,7) -> 6*
       ++0(7,6) -> 6*
       v2() -> 32*
       u0() -> 6*
       v0() -> 6*
       nil0() -> 7*
       6 -> 31*
       7 -> 6*
       20 -> 22*
       32 -> 34*
     problem:
      strict:
       merge(++(x,y),++(u(),v())) -> ++(x,merge(y,++(u(),v())))
      weak:
       merge(++(x,y),++(u(),v())) -> ++(u(),merge(++(x,y),v()))
       merge(x,nil()) -> x
       merge(nil(),y) -> y
     Matrix Interpretation Processor:
      dimension: 2
      max_matrix:
       [1 1]
       [0 1]
       interpretation:
              [0]
        [v] = [1],
        
              [0]
        [u] = [0],
        
                       [1 0]          [0]
        [++](x0, x1) = [0 0]x0 + x1 + [1],
        
                          [1 1]     [1 1]  
        [merge](x0, x1) = [0 1]x0 + [0 1]x1,
        
                [0]
        [nil] = [0]
       orientation:
                                     [1 0]    [1 1]    [3]    [1 0]    [1 1]    [2]                             
        merge(++(x,y),++(u(),v())) = [0 0]x + [0 1]y + [3] >= [0 0]x + [0 1]y + [3] = ++(x,merge(y,++(u(),v())))
        
                                     [1 0]    [1 1]    [3]    [1 0]    [1 1]    [2]                             
        merge(++(x,y),++(u(),v())) = [0 0]x + [0 1]y + [3] >= [0 0]x + [0 1]y + [3] = ++(u(),merge(++(x,y),v()))
        
                         [1 1]          
        merge(x,nil()) = [0 1]x >= x = x
        
                         [1 1]          
        merge(nil(),y) = [0 1]y >= y = y
       problem:
        strict:
         
        weak:
         merge(++(x,y),++(u(),v())) -> ++(x,merge(y,++(u(),v())))
         merge(++(x,y),++(u(),v())) -> ++(u(),merge(++(x,y),v()))
         merge(x,nil()) -> x
         merge(nil(),y) -> y
       Qed