WORST_CASE(?,O(n^1))
* Step 1: NaturalPI WORST_CASE(?,O(n^1))
    + Considered Problem:
        - Strict TRS:
            goal(xs,ys) -> merge(xs,ys)
            merge(Cons(x,xs),Nil()) -> Cons(x,xs)
            merge(Cons(x',xs'),Cons(x,xs)) -> merge[Ite](<=(x',x),Cons(x',xs'),Cons(x,xs))
            merge(Nil(),ys) -> ys
        - Weak TRS:
            <=(0(),y) -> True()
            <=(S(x),0()) -> False()
            <=(S(x),S(y)) -> <=(x,y)
            merge[Ite](False(),xs',Cons(x,xs)) -> Cons(x,merge(xs',xs))
            merge[Ite](True(),Cons(x,xs),ys) -> Cons(x,merge(xs,ys))
        - Signature:
            {<=/2,goal/2,merge/2,merge[Ite]/3} / {0/0,Cons/2,False/0,Nil/0,S/1,True/0}
        - Obligation:
            innermost runtime complexity wrt. defined symbols {<=,goal,merge,merge[Ite]} and constructors {0,Cons,False
            ,Nil,S,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:
          uargs(Cons) = {2},
          uargs(merge[Ite]) = {1}
        
        Following symbols are considered usable:
          {<=,goal,merge,merge[Ite]}
        TcT has computed the following interpretation:
                   p(0) = 2                 
                  p(<=) = 1                 
                p(Cons) = 2 + x2            
               p(False) = 0                 
                 p(Nil) = 2                 
                   p(S) = 0                 
                p(True) = 1                 
                p(goal) = 12 + 7*x1 + 8*x2  
               p(merge) = 8 + 5*x1 + 5*x2   
          p(merge[Ite]) = 4*x1 + 5*x2 + 5*x3
        
        Following rules are strictly oriented:
                           goal(xs,ys) = 12 + 7*xs + 8*ys                            
                                       > 8 + 5*xs + 5*ys                             
                                       = merge(xs,ys)                                
        
               merge(Cons(x,xs),Nil()) = 28 + 5*xs                                   
                                       > 2 + xs                                      
                                       = Cons(x,xs)                                  
        
        merge(Cons(x',xs'),Cons(x,xs)) = 28 + 5*xs + 5*xs'                           
                                       > 24 + 5*xs + 5*xs'                           
                                       = merge[Ite](<=(x',x),Cons(x',xs'),Cons(x,xs))
        
                       merge(Nil(),ys) = 18 + 5*ys                                   
                                       > ys                                          
                                       = ys                                          
        
        
        Following rules are (at-least) weakly oriented:
                                 <=(0(),y) =  1                    
                                           >= 1                    
                                           =  True()               
        
                              <=(S(x),0()) =  1                    
                                           >= 0                    
                                           =  False()              
        
                             <=(S(x),S(y)) =  1                    
                                           >= 1                    
                                           =  <=(x,y)              
        
        merge[Ite](False(),xs',Cons(x,xs)) =  10 + 5*xs + 5*xs'    
                                           >= 10 + 5*xs + 5*xs'    
                                           =  Cons(x,merge(xs',xs))
        
          merge[Ite](True(),Cons(x,xs),ys) =  14 + 5*xs + 5*ys     
                                           >= 10 + 5*xs + 5*ys     
                                           =  Cons(x,merge(xs,ys)) 
        

WORST_CASE(?,O(n^1))