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

WORST_CASE(?,O(n^1))