WORST_CASE(?,O(n^1))
* Step 1: NaturalMI 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:
        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(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) = [8]                  
                p(Cons) = [1] x1 + [1] x2 + [2]
                 p(Nil) = [1]                  
                   p(S) = [1] x1 + [4]         
            p(comp_f_g) = [1] x1 + [1] x2 + [1]
          p(comp_f_g#1) = [2] x1 + [2] x2 + [0]
             p(foldr#3) = [1] x1 + [6]         
           p(foldr_f#3) = [2] x1 + [14]        
                  p(id) = [6]                  
                p(main) = [4] x1 + [15]        
               p(map#2) = [2] x1 + [0]         
              p(plus_x) = [1] x1 + [0]         
            p(plus_x#1) = [2] x1 + [1] x2 + [0]
        
        Following rules are strictly oriented:
        comp_f_g#1(plus_x(x3),comp_f_g(x1,x2),0()) = [2] x1 + [2] x2 + [2] x3 + [2]    
                                                   > [2] x1 + [2] x2 + [2] x3 + [0]    
                                                   = plus_x#1(x3,comp_f_g#1(x1,x2,0()))
        
                   comp_f_g#1(plus_x(x3),id(),0()) = [2] x3 + [12]                     
                                                   > [2] x3 + [8]                      
                                                   = plus_x#1(x3,0())                  
        
                             foldr#3(Cons(x32,x6)) = [1] x32 + [1] x6 + [8]            
                                                   > [1] x32 + [1] x6 + [7]            
                                                   = comp_f_g(x32,foldr#3(x6))         
        
                                    foldr#3(Nil()) = [7]                               
                                                   > [6]                               
                                                   = id()                              
        
                       foldr_f#3(Cons(x16,x5),x24) = [2] x16 + [2] x5 + [18]           
                                                   > [2] x16 + [2] x5 + [12]           
                                                   = comp_f_g#1(x16,foldr#3(x5),x24)   
        
                              foldr_f#3(Nil(),0()) = [16]                              
                                                   > [8]                               
                                                   = 0()                               
        
                                          main(x3) = [4] x3 + [15]                     
                                                   > [4] x3 + [14]                     
                                                   = foldr_f#3(map#2(x3),0())          
        
                               map#2(Cons(x16,x6)) = [2] x16 + [2] x6 + [4]            
                                                   > [1] x16 + [2] x6 + [2]            
                                                   = Cons(plus_x(x16),map#2(x6))       
        
                                      map#2(Nil()) = [2]                               
                                                   > [1]                               
                                                   = Nil()                             
        
                                  plus_x#1(0(),x6) = [1] x6 + [16]                     
                                                   > [1] x6 + [0]                      
                                                   = x6                                
        
                               plus_x#1(S(x8),x10) = [1] x10 + [2] x8 + [8]            
                                                   > [1] x10 + [2] x8 + [4]            
                                                   = S(plus_x#1(x8,x10))               
        
        
        Following rules are (at-least) weakly oriented:
        

WORST_CASE(?,O(n^1))