WORST_CASE(?,O(n^2))
* Step 1: NaturalPI WORST_CASE(?,O(n^2))
    + Considered Problem:
        - Strict TRS:
            *(@x,@y) -> #mult(@x,@y)
            dyade(@l1,@l2) -> dyade#1(@l1,@l2)
            dyade#1(::(@x,@xs),@l2) -> ::(mult(@x,@l2),dyade(@xs,@l2))
            dyade#1(nil(),@l2) -> nil()
            mult(@n,@l) -> mult#1(@l,@n)
            mult#1(::(@x,@xs),@n) -> ::(*(@n,@x),mult(@n,@xs))
            mult#1(nil(),@n) -> nil()
        - Weak TRS:
            #add(#0(),@y) -> @y
            #add(#neg(#s(#0())),@y) -> #pred(@y)
            #add(#neg(#s(#s(@x))),@y) -> #pred(#add(#pos(#s(@x)),@y))
            #add(#pos(#s(#0())),@y) -> #succ(@y)
            #add(#pos(#s(#s(@x))),@y) -> #succ(#add(#pos(#s(@x)),@y))
            #mult(#0(),#0()) -> #0()
            #mult(#0(),#neg(@y)) -> #0()
            #mult(#0(),#pos(@y)) -> #0()
            #mult(#neg(@x),#0()) -> #0()
            #mult(#neg(@x),#neg(@y)) -> #pos(#natmult(@x,@y))
            #mult(#neg(@x),#pos(@y)) -> #neg(#natmult(@x,@y))
            #mult(#pos(@x),#0()) -> #0()
            #mult(#pos(@x),#neg(@y)) -> #neg(#natmult(@x,@y))
            #mult(#pos(@x),#pos(@y)) -> #pos(#natmult(@x,@y))
            #natmult(#0(),@y) -> #0()
            #natmult(#s(@x),@y) -> #add(#pos(@y),#natmult(@x,@y))
            #pred(#0()) -> #neg(#s(#0()))
            #pred(#neg(#s(@x))) -> #neg(#s(#s(@x)))
            #pred(#pos(#s(#0()))) -> #0()
            #pred(#pos(#s(#s(@x)))) -> #pos(#s(@x))
            #succ(#0()) -> #pos(#s(#0()))
            #succ(#neg(#s(#0()))) -> #0()
            #succ(#neg(#s(#s(@x)))) -> #neg(#s(@x))
            #succ(#pos(#s(@x))) -> #pos(#s(#s(@x)))
        - Signature:
            {#add/2,#mult/2,#natmult/2,#pred/1,#succ/1,*/2,dyade/2,dyade#1/2,mult/2,mult#1/2} / {#0/0,#neg/1,#pos/1,#s/1
            ,::/2,nil/0}
        - Obligation:
            innermost runtime complexity wrt. defined symbols {#add,#mult,#natmult,#pred,#succ,*,dyade,dyade#1,mult
            ,mult#1} and constructors {#0,#neg,#pos,#s,::,nil}
    + 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(#add) = {2},
          uargs(#neg) = {1},
          uargs(#pos) = {1},
          uargs(#pred) = {1},
          uargs(#succ) = {1},
          uargs(::) = {1,2}
        
        Following symbols are considered usable:
          {#add,#mult,#natmult,#pred,#succ,*,dyade,dyade#1,mult,mult#1}
        TcT has computed the following interpretation:
                p(#0) = 0                 
              p(#add) = x2                
             p(#mult) = x1*x2             
          p(#natmult) = 0                 
              p(#neg) = x1                
              p(#pos) = x1                
             p(#pred) = x1                
                p(#s) = 0                 
             p(#succ) = x1                
                 p(*) = 1 + x1 + 2*x1*x2  
                p(::) = 2 + x1 + x2       
             p(dyade) = 1 + 3*x1 + 3*x1*x2
           p(dyade#1) = 3*x1 + 3*x1*x2    
              p(mult) = 1 + 2*x1*x2 + 3*x2
            p(mult#1) = 3*x1 + 2*x1*x2    
               p(nil) = 2                 
        
        Following rules are strictly oriented:
                       *(@x,@y) = 1 + @x + 2*@x*@y                               
                                > @x*@y                                          
                                = #mult(@x,@y)                                   
        
                 dyade(@l1,@l2) = 1 + 3*@l1 + 3*@l1*@l2                          
                                > 3*@l1 + 3*@l1*@l2                              
                                = dyade#1(@l1,@l2)                               
        
        dyade#1(::(@x,@xs),@l2) = 6 + 6*@l2 + 3*@l2*@x + 3*@l2*@xs + 3*@x + 3*@xs
                                > 4 + 3*@l2 + 2*@l2*@x + 3*@l2*@xs + 3*@xs       
                                = ::(mult(@x,@l2),dyade(@xs,@l2))                
        
             dyade#1(nil(),@l2) = 6 + 6*@l2                                      
                                > 2                                              
                                = nil()                                          
        
                    mult(@n,@l) = 1 + 3*@l + 2*@l*@n                             
                                > 3*@l + 2*@l*@n                                 
                                = mult#1(@l,@n)                                  
        
          mult#1(::(@x,@xs),@n) = 6 + 4*@n + 2*@n*@x + 2*@n*@xs + 3*@x + 3*@xs   
                                > 4 + @n + 2*@n*@x + 2*@n*@xs + 3*@xs            
                                = ::(*(@n,@x),mult(@n,@xs))                      
        
               mult#1(nil(),@n) = 6 + 4*@n                                       
                                > 2                                              
                                = nil()                                          
        
        
        Following rules are (at-least) weakly oriented:
                    #add(#0(),@y) =  @y                            
                                  >= @y                            
                                  =  @y                            
        
          #add(#neg(#s(#0())),@y) =  @y                            
                                  >= @y                            
                                  =  #pred(@y)                     
        
        #add(#neg(#s(#s(@x))),@y) =  @y                            
                                  >= @y                            
                                  =  #pred(#add(#pos(#s(@x)),@y))  
        
          #add(#pos(#s(#0())),@y) =  @y                            
                                  >= @y                            
                                  =  #succ(@y)                     
        
        #add(#pos(#s(#s(@x))),@y) =  @y                            
                                  >= @y                            
                                  =  #succ(#add(#pos(#s(@x)),@y))  
        
                 #mult(#0(),#0()) =  0                             
                                  >= 0                             
                                  =  #0()                          
        
             #mult(#0(),#neg(@y)) =  0                             
                                  >= 0                             
                                  =  #0()                          
        
             #mult(#0(),#pos(@y)) =  0                             
                                  >= 0                             
                                  =  #0()                          
        
             #mult(#neg(@x),#0()) =  0                             
                                  >= 0                             
                                  =  #0()                          
        
         #mult(#neg(@x),#neg(@y)) =  @x*@y                         
                                  >= 0                             
                                  =  #pos(#natmult(@x,@y))         
        
         #mult(#neg(@x),#pos(@y)) =  @x*@y                         
                                  >= 0                             
                                  =  #neg(#natmult(@x,@y))         
        
             #mult(#pos(@x),#0()) =  0                             
                                  >= 0                             
                                  =  #0()                          
        
         #mult(#pos(@x),#neg(@y)) =  @x*@y                         
                                  >= 0                             
                                  =  #neg(#natmult(@x,@y))         
        
         #mult(#pos(@x),#pos(@y)) =  @x*@y                         
                                  >= 0                             
                                  =  #pos(#natmult(@x,@y))         
        
                #natmult(#0(),@y) =  0                             
                                  >= 0                             
                                  =  #0()                          
        
              #natmult(#s(@x),@y) =  0                             
                                  >= 0                             
                                  =  #add(#pos(@y),#natmult(@x,@y))
        
                      #pred(#0()) =  0                             
                                  >= 0                             
                                  =  #neg(#s(#0()))                
        
              #pred(#neg(#s(@x))) =  0                             
                                  >= 0                             
                                  =  #neg(#s(#s(@x)))              
        
            #pred(#pos(#s(#0()))) =  0                             
                                  >= 0                             
                                  =  #0()                          
        
          #pred(#pos(#s(#s(@x)))) =  0                             
                                  >= 0                             
                                  =  #pos(#s(@x))                  
        
                      #succ(#0()) =  0                             
                                  >= 0                             
                                  =  #pos(#s(#0()))                
        
            #succ(#neg(#s(#0()))) =  0                             
                                  >= 0                             
                                  =  #0()                          
        
          #succ(#neg(#s(#s(@x)))) =  0                             
                                  >= 0                             
                                  =  #neg(#s(@x))                  
        
              #succ(#pos(#s(@x))) =  0                             
                                  >= 0                             
                                  =  #pos(#s(#s(@x)))              
        

WORST_CASE(?,O(n^2))