YES
O(n)
TRS:
 {
           not(false()) -> true(),
            not(true()) -> false(),
        evenodd(x, 0()) -> not(evenodd(x, s(0()))),
  evenodd(s(x), s(0())) -> evenodd(x, 0()),
   evenodd(0(), s(0())) -> false()
 }
 DUP: We consider a non-duplicating system.
  Trs:
   {
             not(false()) -> true(),
              not(true()) -> false(),
          evenodd(x, 0()) -> not(evenodd(x, s(0()))),
    evenodd(s(x), s(0())) -> evenodd(x, 0()),
     evenodd(0(), s(0())) -> false()
   }
  BOUND:
   Automaton:
    {
                0_2() -> 11,
                0_1() -> 7,
                0_0() -> 6,
              s_2(11) -> 12,
               s_1(7) -> 9,
               s_0(6) -> 6,
     evenodd_2(6, 12) -> 13,
      evenodd_1(6, 9) -> 10,
      evenodd_1(6, 7) -> 13 | 10 | 6,
      evenodd_0(6, 6) -> 6,
             true_3() -> 13 | 10 | 6,
             true_2() -> 13 | 10 | 6,
             true_1() -> 6,
             true_0() -> 6,
            not_2(13) -> 13 | 10 | 6,
            not_1(10) -> 6,
             not_0(6) -> 6,
            false_3() -> 13 | 10 | 6,
            false_2() -> 6,
            false_1() -> 13 | 10 | 6,
            false_0() -> 6
    }
   Strict:
    {}
   Qed