WORST_CASE(?,O(n^1))
* Step 1: NaturalPI WORST_CASE(?,O(n^1))
    + Considered Problem:
        - Strict TRS:
            append(@l1,@l2) -> append#1(@l1,@l2)
            append#1(::(@x,@xs),@l2) -> ::(@x,append(@xs,@l2))
            append#1(nil(),@l2) -> @l2
            appendAll(@l) -> appendAll#1(@l)
            appendAll#1(::(@l1,@ls)) -> append(@l1,appendAll(@ls))
            appendAll#1(nil()) -> nil()
            appendAll2(@l) -> appendAll2#1(@l)
            appendAll2#1(::(@l1,@ls)) -> append(appendAll(@l1),appendAll2(@ls))
            appendAll2#1(nil()) -> nil()
            appendAll3(@l) -> appendAll3#1(@l)
            appendAll3#1(::(@l1,@ls)) -> append(appendAll2(@l1),appendAll3(@ls))
            appendAll3#1(nil()) -> nil()
        - Signature:
            {append/2,append#1/2,appendAll/1,appendAll#1/1,appendAll2/1,appendAll2#1/1,appendAll3/1
            ,appendAll3#1/1} / {::/2,nil/0}
        - Obligation:
            innermost runtime complexity wrt. defined symbols {append,append#1,appendAll,appendAll#1,appendAll2
            ,appendAll2#1,appendAll3,appendAll3#1} and constructors {::,nil}
    + 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(::) = {2},
          uargs(append) = {1,2}
        
        Following symbols are considered usable:
          {append,append#1,appendAll,appendAll#1,appendAll2,appendAll2#1,appendAll3,appendAll3#1}
        TcT has computed the following interpretation:
                    p(::) = 2 + x1 + x2  
                p(append) = 1 + 2*x1 + x2
              p(append#1) = 2*x1 + x2    
             p(appendAll) = 1 + 2*x1     
           p(appendAll#1) = 2*x1         
            p(appendAll2) = 13 + 5*x1    
          p(appendAll2#1) = 10 + 5*x1    
            p(appendAll3) = 3 + 15*x1    
          p(appendAll3#1) = 1 + 15*x1    
                   p(nil) = 2            
        
        Following rules are strictly oriented:
                  append(@l1,@l2) = 1 + 2*@l1 + @l2                        
                                  > 2*@l1 + @l2                            
                                  = append#1(@l1,@l2)                      
        
         append#1(::(@x,@xs),@l2) = 4 + @l2 + 2*@x + 2*@xs                 
                                  > 3 + @l2 + @x + 2*@xs                   
                                  = ::(@x,append(@xs,@l2))                 
        
              append#1(nil(),@l2) = 4 + @l2                                
                                  > @l2                                    
                                  = @l2                                    
        
                    appendAll(@l) = 1 + 2*@l                               
                                  > 2*@l                                   
                                  = appendAll#1(@l)                        
        
         appendAll#1(::(@l1,@ls)) = 4 + 2*@l1 + 2*@ls                      
                                  > 2 + 2*@l1 + 2*@ls                      
                                  = append(@l1,appendAll(@ls))             
        
               appendAll#1(nil()) = 4                                      
                                  > 2                                      
                                  = nil()                                  
        
                   appendAll2(@l) = 13 + 5*@l                              
                                  > 10 + 5*@l                              
                                  = appendAll2#1(@l)                       
        
        appendAll2#1(::(@l1,@ls)) = 20 + 5*@l1 + 5*@ls                     
                                  > 16 + 4*@l1 + 5*@ls                     
                                  = append(appendAll(@l1),appendAll2(@ls)) 
        
              appendAll2#1(nil()) = 20                                     
                                  > 2                                      
                                  = nil()                                  
        
                   appendAll3(@l) = 3 + 15*@l                              
                                  > 1 + 15*@l                              
                                  = appendAll3#1(@l)                       
        
        appendAll3#1(::(@l1,@ls)) = 31 + 15*@l1 + 15*@ls                   
                                  > 30 + 10*@l1 + 15*@ls                   
                                  = append(appendAll2(@l1),appendAll3(@ls))
        
              appendAll3#1(nil()) = 31                                     
                                  > 2                                      
                                  = nil()                                  
        
        
        Following rules are (at-least) weakly oriented:
        

WORST_CASE(?,O(n^1))