YES(?,O(n^2))

Problem:
 app(nil(),xs) -> nil()
 app(cons(x,xs),ys) -> cons(x,app(xs,ys))

Proof:
 Matrix Interpretation Processor:
  dimension: 2
  interpretation:
                    [1 8]          [10]
   [cons](x0, x1) = [0 0]x0 + x1 + [1 ],
   
                   [1 1]     [1 2]  
   [app](x0, x1) = [0 1]x0 + [0 0]x1,
   
           [4]
   [nil] = [8]
  orientation:
                   [1 2]     [12]    [4]        
   app(nil(),xs) = [0 0]xs + [8 ] >= [8] = nil()
   
                        [1 8]    [1 1]     [1 2]     [11]    [1 8]    [1 1]     [1 2]     [10]                     
   app(cons(x,xs),ys) = [0 0]x + [0 1]xs + [0 0]ys + [1 ] >= [0 0]x + [0 1]xs + [0 0]ys + [1 ] = cons(x,app(xs,ys))
  problem:
   
  Qed