WORST_CASE(?,O(n^2))
* Step 1: NaturalPI WORST_CASE(?,O(n^2))
    + Considered Problem:
        - Strict TRS:
            main(x5,x12) -> map#2(plus_x(x12),x5)
            map#2(plus_x(x2),Nil()) -> Nil()
            map#2(plus_x(x6),Cons(x4,x2)) -> Cons(plus_x#1(x6,x4),map#2(plus_x(x6),x2))
            plus_x#1(0(),x8) -> x8
            plus_x#1(S(x12),x14) -> S(plus_x#1(x12,x14))
        - Signature:
            {main/2,map#2/2,plus_x#1/2} / {0/0,Cons/2,Nil/0,S/1,plus_x/1}
        - Obligation:
            innermost runtime complexity wrt. defined symbols {main,map#2,plus_x#1} and constructors {0,Cons,Nil,S
            ,plus_x}
    + 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(Cons) = {1,2},
          uargs(S) = {1}
        
        Following symbols are considered usable:
          {main,map#2,plus_x#1}
        TcT has computed the following interpretation:
                 p(0) = 0                                        
              p(Cons) = 2 + x1 + x2                              
               p(Nil) = 3                                        
                 p(S) = 2 + x1                                   
              p(main) = 6 + 4*x1 + 4*x1*x2 + x1^2 + 7*x2 + 3*x2^2
             p(map#2) = 3 + 6*x1 + 3*x1*x2 + 2*x1^2 + 3*x2       
            p(plus_x) = x1                                       
          p(plus_x#1) = 2 + 5*x1 + 2*x2                          
        
        Following rules are strictly oriented:
                         main(x5,x12) = 6 + 7*x12 + 4*x12*x5 + 3*x12^2 + 4*x5 + x5^2        
                                      > 3 + 6*x12 + 3*x12*x5 + 2*x12^2 + 3*x5               
                                      = map#2(plus_x(x12),x5)                               
        
              map#2(plus_x(x2),Nil()) = 12 + 15*x2 + 2*x2^2                                 
                                      > 3                                                   
                                      = Nil()                                               
        
        map#2(plus_x(x6),Cons(x4,x2)) = 9 + 3*x2 + 3*x2*x6 + 3*x4 + 3*x4*x6 + 12*x6 + 2*x6^2
                                      > 7 + 3*x2 + 3*x2*x6 + 2*x4 + 11*x6 + 2*x6^2          
                                      = Cons(plus_x#1(x6,x4),map#2(plus_x(x6),x2))          
        
                     plus_x#1(0(),x8) = 2 + 2*x8                                            
                                      > x8                                                  
                                      = x8                                                  
        
                 plus_x#1(S(x12),x14) = 12 + 5*x12 + 2*x14                                  
                                      > 4 + 5*x12 + 2*x14                                   
                                      = S(plus_x#1(x12,x14))                                
        
        
        Following rules are (at-least) weakly oriented:
        

WORST_CASE(?,O(n^2))