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

WORST_CASE(?,O(n^1))