WORST_CASE(?,O(n^1))
* Step 1: NaturalMI 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:
        NaturalMI {miDimension = 1, miDegree = 1, miKind = Algebraic, uargs = UArgs, urules = URules, selector = Nothing}
    + Details:
        We apply a matrix interpretation of kind constructor based matrix interpretation:
        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) = [0]                           
                  p(<=) = [0]                           
                p(Cons) = [1] x2 + [5]                  
               p(False) = [0]                           
                 p(Nil) = [8]                           
                   p(S) = [1] x1 + [1]                  
                p(True) = [0]                           
                p(goal) = [2] x1 + [8] x2 + [9]         
               p(merge) = [2] x1 + [2] x2 + [1]         
          p(merge[Ite]) = [8] x1 + [2] x2 + [2] x3 + [0]
        
        Following rules are strictly oriented:
                           goal(xs,ys) = [2] xs + [8] ys + [9]                       
                                       > [2] xs + [2] ys + [1]                       
                                       = merge(xs,ys)                                
        
               merge(Cons(x,xs),Nil()) = [2] xs + [27]                               
                                       > [1] xs + [5]                                
                                       = Cons(x,xs)                                  
        
        merge(Cons(x',xs'),Cons(x,xs)) = [2] xs + [2] xs' + [21]                     
                                       > [2] xs + [2] xs' + [20]                     
                                       = merge[Ite](<=(x',x),Cons(x',xs'),Cons(x,xs))
        
                       merge(Nil(),ys) = [2] ys + [17]                               
                                       > [1] ys + [0]                                
                                       = ys                                          
        
        
        Following rules are (at-least) weakly oriented:
                                 <=(0(),y) =  [0]                    
                                           >= [0]                    
                                           =  True()                 
        
                              <=(S(x),0()) =  [0]                    
                                           >= [0]                    
                                           =  False()                
        
                             <=(S(x),S(y)) =  [0]                    
                                           >= [0]                    
                                           =  <=(x,y)                
        
        merge[Ite](False(),xs',Cons(x,xs)) =  [2] xs + [2] xs' + [10]
                                           >= [2] xs + [2] xs' + [6] 
                                           =  Cons(x,merge(xs',xs))  
        
          merge[Ite](True(),Cons(x,xs),ys) =  [2] xs + [2] ys + [10] 
                                           >= [2] xs + [2] ys + [6]  
                                           =  Cons(x,merge(xs,ys))   
        

WORST_CASE(?,O(n^1))