YES(?,O(1))

We are left with following problem, upon which TcT provides the
certificate YES(?,O(1)).

Strict Trs:
  { primes() -> sieve(from(s(s(0()))))
  , sieve(cons(X, Y)) -> cons(X, n__filter(X, sieve(activate(Y))))
  , from(X) -> cons(X, n__from(s(X)))
  , from(X) -> n__from(X)
  , cons(X1, X2) -> n__cons(X1, X2)
  , head(cons(X, Y)) -> X
  , tail(cons(X, Y)) -> activate(Y)
  , activate(X) -> X
  , activate(n__from(X)) -> from(X)
  , activate(n__filter(X1, X2)) -> filter(X1, X2)
  , activate(n__cons(X1, X2)) -> cons(X1, X2)
  , if(true(), X, Y) -> activate(X)
  , if(false(), X, Y) -> activate(Y)
  , filter(X1, X2) -> n__filter(X1, X2)
  , filter(s(s(X)), cons(Y, Z)) ->
    if(divides(s(s(X)), Y),
       n__filter(s(s(X)), activate(Z)),
       n__cons(Y, n__filter(X, sieve(Y)))) }
Obligation:
  innermost runtime complexity
Answer:
  YES(?,O(1))

Arguments of following rules are not normal-forms:

{ sieve(cons(X, Y)) -> cons(X, n__filter(X, sieve(activate(Y))))
, head(cons(X, Y)) -> X
, tail(cons(X, Y)) -> activate(Y)
, filter(s(s(X)), cons(Y, Z)) ->
  if(divides(s(s(X)), Y),
     n__filter(s(s(X)), activate(Z)),
     n__cons(Y, n__filter(X, sieve(Y)))) }

All above mentioned rules can be savely removed.

We are left with following problem, upon which TcT provides the
certificate YES(?,O(1)).

Strict Trs:
  { primes() -> sieve(from(s(s(0()))))
  , from(X) -> cons(X, n__from(s(X)))
  , from(X) -> n__from(X)
  , cons(X1, X2) -> n__cons(X1, X2)
  , activate(X) -> X
  , activate(n__from(X)) -> from(X)
  , activate(n__filter(X1, X2)) -> filter(X1, X2)
  , activate(n__cons(X1, X2)) -> cons(X1, X2)
  , if(true(), X, Y) -> activate(X)
  , if(false(), X, Y) -> activate(Y)
  , filter(X1, X2) -> n__filter(X1, X2) }
Obligation:
  innermost runtime complexity
Answer:
  YES(?,O(1))

The input was oriented with the instance of 'Small Polynomial Path
Order (PS,0-bounded)' as induced by the safe mapping

 safe(primes) = {}, safe(sieve) = {}, safe(from) = {1},
 safe(s) = {1}, safe(0) = {}, safe(cons) = {1, 2},
 safe(n__from) = {1}, safe(head) = {}, safe(tail) = {},
 safe(activate) = {}, safe(if) = {1}, safe(true) = {},
 safe(false) = {}, safe(filter) = {1, 2}, safe(divides) = {1, 2},
 safe(n__filter) = {1, 2}, safe(n__cons) = {1, 2}

and precedence

 primes > from, primes > cons, primes > activate, primes > filter,
 from > cons, activate > from, activate > cons, activate > filter,
 if > from, if > cons, if > activate, if > filter, filter > cons,
 primes ~ if, from ~ filter .

Following symbols are considered recursive:

 {}

The recursion depth is 0.

For your convenience, here are the satisfied ordering constraints:

                         primes() > sieve(from(; s(; s(; 0())));)
                                                                 
                        from(; X) > cons(; X,  n__from(; s(; X)))
                                                                 
                        from(; X) > n__from(; X)                 
                                                                 
                  cons(; X1,  X2) > n__cons(; X1,  X2)           
                                                                 
                     activate(X;) > X                            
                                                                 
          activate(n__from(; X);) > from(; X)                    
                                                                 
  activate(n__filter(; X1,  X2);) > filter(; X1,  X2)            
                                                                 
    activate(n__cons(; X1,  X2);) > cons(; X1,  X2)              
                                                                 
                if(X,  Y; true()) > activate(X;)                 
                                                                 
               if(X,  Y; false()) > activate(Y;)                 
                                                                 
                filter(; X1,  X2) > n__filter(; X1,  X2)         
                                                                 

Hurray, we answered YES(?,O(1))