YES(?,O(n^1))
TRS:
 {
                f X -> if(X, c(), n__f true()),
                f X -> n__f X,
   if(true(), X, Y) -> X,
  if(false(), X, Y) -> activate Y,
         activate X -> X,
    activate n__f X -> f X
 }
 DUP: We consider a non-duplicating system.
  Trs:
   {
                  f X -> if(X, c(), n__f true()),
                  f X -> n__f X,
     if(true(), X, Y) -> X,
    if(false(), X, Y) -> activate Y,
           activate X -> X,
      activate n__f X -> f X
   }
  Natural interpretation:
   Strict:
    {
                   f X -> if(X, c(), n__f true()),
                   f X -> n__f X,
      if(true(), X, Y) -> X,
     if(false(), X, Y) -> activate Y,
            activate X -> X,
       activate n__f X -> f X
    }
   Weak:
    {}
   Interpretation class: stronglylinear
   [false] = + 7
   [activate](X0) = + 1*X0 + 6
   [true] = + 1
   [n__f](X0) = + 1*X0 + 0
   [c] = + 0
   [if](X2, X1, X0) = + 1*X0 + 1*X1 + 1*X2 + 0
   [f](X0) = + 1*X0 + 4
   
   Qed