WORST_CASE(?,O(n^1))
* Step 1: NaturalPI WORST_CASE(?,O(n^1))
    + Considered Problem:
        - Strict TRS:
            even(Cons(x,xs)) -> odd(xs)
            even(Nil()) -> True()
            evenodd(x) -> even(x)
            notEmpty(Cons(x,xs)) -> True()
            notEmpty(Nil()) -> False()
            odd(Cons(x,xs)) -> even(xs)
            odd(Nil()) -> False()
        - Signature:
            {even/1,evenodd/1,notEmpty/1,odd/1} / {Cons/2,False/0,Nil/0,True/0}
        - Obligation:
            innermost runtime complexity wrt. defined symbols {even,evenodd,notEmpty,odd} and constructors {Cons,False
            ,Nil,True}
    + Applied Processor:
        NaturalPI {shape = Linear, restrict = NoRestrict, uargs = UArgs, urules = URules, selector = Nothing}
    + Details:
        We apply a polynomial interpretation of kind constructor-based(linear):
        The following argument positions are considered usable:
          none
        
        Following symbols are considered usable:
          {even,evenodd,notEmpty,odd}
        TcT has computed the following interpretation:
              p(Cons) = 9 + x1 + x2
             p(False) = 5          
               p(Nil) = 8          
              p(True) = 7          
              p(even) = 7 + x1     
           p(evenodd) = 15 + 12*x1 
          p(notEmpty) = 12         
               p(odd) = 6 + x1     
        
        Following rules are strictly oriented:
            even(Cons(x,xs)) = 16 + x + xs
                             > 6 + xs     
                             = odd(xs)    
        
                 even(Nil()) = 15         
                             > 7          
                             = True()     
        
                  evenodd(x) = 15 + 12*x  
                             > 7 + x      
                             = even(x)    
        
        notEmpty(Cons(x,xs)) = 12         
                             > 7          
                             = True()     
        
             notEmpty(Nil()) = 12         
                             > 5          
                             = False()    
        
             odd(Cons(x,xs)) = 15 + x + xs
                             > 7 + xs     
                             = even(xs)   
        
                  odd(Nil()) = 14         
                             > 5          
                             = False()    
        
        
        Following rules are (at-least) weakly oriented:
        

WORST_CASE(?,O(n^1))