WORST_CASE(?,O(n^1))
* Step 1: NaturalPI WORST_CASE(?,O(n^1))
    + Considered Problem:
        - Strict TRS:
            +Full(0(),y) -> y
            +Full(S(x),y) -> +Full(x,S(y))
            f(x) -> *(x,x)
            goal(xs) -> map(xs)
            map(Cons(x,xs)) -> Cons(f(x),map(xs))
            map(Nil()) -> Nil()
        - Weak TRS:
            *(x,0()) -> 0()
            *(x,S(0())) -> x
            *(x,S(S(y))) -> +(x,*(x,S(y)))
            *(0(),y) -> 0()
        - Signature:
            {*/2,+Full/2,f/1,goal/1,map/1} / {+/2,0/0,Cons/2,Nil/0,S/1}
        - Obligation:
            innermost runtime complexity wrt. defined symbols {*,+Full,f,goal,map} and constructors {+,0,Cons,Nil,S}
    + 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(Cons) = {1,2}
        
        Following symbols are considered usable:
          {*,+Full,f,goal,map}
        TcT has computed the following interpretation:
              p(*) = x1 + x2        
              p(+) = x2             
          p(+Full) = 6 + 8*x1 + 7*x2
              p(0) = 0              
           p(Cons) = 2 + x1 + x2    
            p(Nil) = 4              
              p(S) = 2 + x1         
              p(f) = 1 + 2*x1       
           p(goal) = 15 + 8*x1      
            p(map) = 8 + 4*x1       
        
        Following rules are strictly oriented:
           +Full(0(),y) = 6 + 7*y           
                        > y                 
                        = y                 
        
          +Full(S(x),y) = 22 + 8*x + 7*y    
                        > 20 + 8*x + 7*y    
                        = +Full(x,S(y))     
        
                   f(x) = 1 + 2*x           
                        > 2*x               
                        = *(x,x)            
        
               goal(xs) = 15 + 8*xs         
                        > 8 + 4*xs          
                        = map(xs)           
        
        map(Cons(x,xs)) = 16 + 4*x + 4*xs   
                        > 11 + 2*x + 4*xs   
                        = Cons(f(x),map(xs))
        
             map(Nil()) = 24                
                        > 4                 
                        = Nil()             
        
        
        Following rules are (at-least) weakly oriented:
            *(x,0()) =  x             
                     >= 0             
                     =  0()           
        
         *(x,S(0())) =  2 + x         
                     >= x             
                     =  x             
        
        *(x,S(S(y))) =  4 + x + y     
                     >= 2 + x + y     
                     =  +(x,*(x,S(y)))
        
            *(0(),y) =  y             
                     >= 0             
                     =  0()           
        

WORST_CASE(?,O(n^1))