YES
O(n)
TRS:
 {app(app(app(compose(), f), g), x) -> app(f, app(g, x))}
 Natural interpretation:
  Strict:
   {app(app(app(compose(), f), g), x) -> app(f, app(g, x))}
  Weak:
   {}
  Interpretation class: stronglylinear
  [compose] = + 0
  [app](X1, X0) = + 1*X0 + 1*X1 + 1
  
  Qed