WORST_CASE(?,O(n^1))
* Step 1: NaturalPI WORST_CASE(?,O(n^1))
    + Considered Problem:
        - Strict TRS:
            goal(x,xs) -> member(x,xs)
            member(x,Nil()) -> False()
            member(x',Cons(x,xs)) -> member[Ite][True][Ite](!EQ(x',x),x',Cons(x,xs))
            notEmpty(Cons(x,xs)) -> True()
            notEmpty(Nil()) -> False()
        - Weak TRS:
            !EQ(0(),0()) -> True()
            !EQ(0(),S(y)) -> False()
            !EQ(S(x),0()) -> False()
            !EQ(S(x),S(y)) -> !EQ(x,y)
            member[Ite][True][Ite](False(),x',Cons(x,xs)) -> member(x',xs)
            member[Ite][True][Ite](True(),x,xs) -> True()
        - Signature:
            {!EQ/2,goal/2,member/2,member[Ite][True][Ite]/3,notEmpty/1} / {0/0,Cons/2,False/0,Nil/0,S/1,True/0}
        - Obligation:
            innermost runtime complexity wrt. defined symbols {!EQ,goal,member,member[Ite][True][Ite]
            ,notEmpty} and constructors {0,Cons,False,Nil,S,True}
    + Applied Processor:
        NaturalPI {shape = StronglyLinear, restrict = NoRestrict, uargs = UArgs, urules = URules, selector = Nothing}
    + Details:
        We apply a polynomial interpretation of kind constructor-based(stronglyLinear):
        The following argument positions are considered usable:
          uargs(member[Ite][True][Ite]) = {1}
        
        Following symbols are considered usable:
          {!EQ,goal,member,member[Ite][True][Ite],notEmpty}
        TcT has computed the following interpretation:
                             p(!EQ) = 8           
                               p(0) = 2           
                            p(Cons) = 4 + x2      
                           p(False) = 5           
                             p(Nil) = 0           
                               p(S) = 1           
                            p(True) = 0           
                            p(goal) = 12 + x1 + x2
                          p(member) = 9 + x2      
          p(member[Ite][True][Ite]) = x1 + x3     
                        p(notEmpty) = 15 + x1     
        
        Following rules are strictly oriented:
                   goal(x,xs) = 12 + x + xs                                    
                              > 9 + xs                                         
                              = member(x,xs)                                   
        
              member(x,Nil()) = 9                                              
                              > 5                                              
                              = False()                                        
        
        member(x',Cons(x,xs)) = 13 + xs                                        
                              > 12 + xs                                        
                              = member[Ite][True][Ite](!EQ(x',x),x',Cons(x,xs))
        
         notEmpty(Cons(x,xs)) = 19 + xs                                        
                              > 0                                              
                              = True()                                         
        
              notEmpty(Nil()) = 15                                             
                              > 5                                              
                              = False()                                        
        
        
        Following rules are (at-least) weakly oriented:
                                         !EQ(0(),0()) =  8            
                                                      >= 0            
                                                      =  True()       
        
                                        !EQ(0(),S(y)) =  8            
                                                      >= 5            
                                                      =  False()      
        
                                        !EQ(S(x),0()) =  8            
                                                      >= 5            
                                                      =  False()      
        
                                       !EQ(S(x),S(y)) =  8            
                                                      >= 8            
                                                      =  !EQ(x,y)     
        
        member[Ite][True][Ite](False(),x',Cons(x,xs)) =  9 + xs       
                                                      >= 9 + xs       
                                                      =  member(x',xs)
        
                  member[Ite][True][Ite](True(),x,xs) =  xs           
                                                      >= 0            
                                                      =  True()       
        

WORST_CASE(?,O(n^1))