WORST_CASE(?,O(n^2))
* Step 1: NaturalPI WORST_CASE(?,O(n^2))
    + Considered Problem:
        - Strict TRS:
            goal(xs,ys) -> overlap(xs,ys)
            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()
            overlap(Cons(x,xs),ys) -> overlap[Ite][True][Ite](member(x,ys),Cons(x,xs),ys)
            overlap(Nil(),ys) -> 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()
            overlap[Ite][True][Ite](False(),Cons(x,xs),ys) -> overlap(xs,ys)
            overlap[Ite][True][Ite](True(),xs,ys) -> True()
        - Signature:
            {!EQ/2,goal/2,member/2,member[Ite][True][Ite]/3,notEmpty/1,overlap/2,overlap[Ite][True][Ite]/3} / {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,overlap
            ,overlap[Ite][True][Ite]} and constructors {0,Cons,False,Nil,S,True}
    + Applied Processor:
        NaturalPI {shape = Mixed 2, restrict = NoRestrict, uargs = UArgs, urules = URules, selector = Nothing}
    + Details:
        We apply a polynomial interpretation of kind constructor-based(mixed(2)):
        The following argument positions are considered usable:
          uargs(member[Ite][True][Ite]) = {1},
          uargs(overlap[Ite][True][Ite]) = {1}
        
        Following symbols are considered usable:
          {!EQ,goal,member,member[Ite][True][Ite],notEmpty,overlap,overlap[Ite][True][Ite]}
        TcT has computed the following interpretation:
                              p(!EQ) = 0                               
                                p(0) = 0                               
                             p(Cons) = 1 + x2                          
                            p(False) = 0                               
                              p(Nil) = 0                               
                                p(S) = 2                               
                             p(True) = 0                               
                             p(goal) = 7 + 4*x1*x2 + 5*x1^2 + 5*x2     
                           p(member) = 1 + x2                          
           p(member[Ite][True][Ite]) = 2*x1 + x1*x2 + x3               
                         p(notEmpty) = 4 + x1 + 4*x1^2                 
                          p(overlap) = 4 + 4*x1*x2 + 2*x1^2 + 5*x2     
          p(overlap[Ite][True][Ite]) = 2 + x1 + 4*x2*x3 + 2*x2^2 + 4*x3
        
        Following rules are strictly oriented:
                   goal(xs,ys) = 7 + 4*xs*ys + 5*xs^2 + 5*ys                        
                               > 4 + 4*xs*ys + 2*xs^2 + 5*ys                        
                               = overlap(xs,ys)                                     
        
               member(x,Nil()) = 1                                                  
                               > 0                                                  
                               = False()                                            
        
         member(x',Cons(x,xs)) = 2 + xs                                             
                               > 1 + xs                                             
                               = member[Ite][True][Ite](!EQ(x,x'),x',Cons(x,xs))    
        
          notEmpty(Cons(x,xs)) = 9 + 9*xs + 4*xs^2                                  
                               > 0                                                  
                               = True()                                             
        
               notEmpty(Nil()) = 4                                                  
                               > 0                                                  
                               = False()                                            
        
        overlap(Cons(x,xs),ys) = 6 + 4*xs + 4*xs*ys + 2*xs^2 + 9*ys                 
                               > 5 + 4*xs + 4*xs*ys + 2*xs^2 + 9*ys                 
                               = overlap[Ite][True][Ite](member(x,ys),Cons(x,xs),ys)
        
             overlap(Nil(),ys) = 4 + 5*ys                                           
                               > 0                                                  
                               = False()                                            
        
        
        Following rules are (at-least) weakly oriented:
                                          !EQ(0(),0()) =  0                                 
                                                       >= 0                                 
                                                       =  True()                            
        
                                         !EQ(0(),S(y)) =  0                                 
                                                       >= 0                                 
                                                       =  False()                           
        
                                         !EQ(S(x),0()) =  0                                 
                                                       >= 0                                 
                                                       =  False()                           
        
                                        !EQ(S(x),S(y)) =  0                                 
                                                       >= 0                                 
                                                       =  !EQ(x,y)                          
        
         member[Ite][True][Ite](False(),x',Cons(x,xs)) =  1 + xs                            
                                                       >= 1 + xs                            
                                                       =  member(x',xs)                     
        
                   member[Ite][True][Ite](True(),x,xs) =  xs                                
                                                       >= 0                                 
                                                       =  True()                            
        
        overlap[Ite][True][Ite](False(),Cons(x,xs),ys) =  4 + 4*xs + 4*xs*ys + 2*xs^2 + 8*ys
                                                       >= 4 + 4*xs*ys + 2*xs^2 + 5*ys       
                                                       =  overlap(xs,ys)                    
        
                 overlap[Ite][True][Ite](True(),xs,ys) =  2 + 4*xs*ys + 2*xs^2 + 4*ys       
                                                       >= 0                                 
                                                       =  True()                            
        

WORST_CASE(?,O(n^2))