WORST_CASE(?,O(n^1))
* Step 1: NaturalPI WORST_CASE(?,O(n^1))
    + Considered Problem:
        - Strict TRS:
            -(x,0()) -> x
            -(s(x),s(y)) -> -(x,y)
            double(0()) -> 0()
            double(s(x)) -> s(s(double(x)))
            half(0()) -> 0()
            half(double(x)) -> x
            half(s(0())) -> 0()
            half(s(s(x))) -> s(half(x))
            if(0(),y,z) -> y
            if(s(x),y,z) -> z
        - Signature:
            {-/2,double/1,half/1,if/3} / {0/0,s/1}
        - Obligation:
            innermost runtime complexity wrt. defined symbols {-,double,half,if} and constructors {0,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}
        
        Following symbols are considered usable:
          {-,double,half,if}
        TcT has computed the following interpretation:
               p(-) = 4 + 4*x1              
               p(0) = 6                     
          p(double) = 1 + 4*x1              
            p(half) = 3*x1                  
              p(if) = 4 + 4*x1 + 8*x2 + 8*x3
               p(s) = 4 + x1                
        
        Following rules are strictly oriented:
               -(x,0()) = 4 + 4*x             
                        > x                   
                        = x                   
        
           -(s(x),s(y)) = 20 + 4*x            
                        > 4 + 4*x             
                        = -(x,y)              
        
            double(0()) = 25                  
                        > 6                   
                        = 0()                 
        
           double(s(x)) = 17 + 4*x            
                        > 9 + 4*x             
                        = s(s(double(x)))     
        
              half(0()) = 18                  
                        > 6                   
                        = 0()                 
        
        half(double(x)) = 3 + 12*x            
                        > x                   
                        = x                   
        
           half(s(0())) = 30                  
                        > 6                   
                        = 0()                 
        
          half(s(s(x))) = 24 + 3*x            
                        > 4 + 3*x             
                        = s(half(x))          
        
            if(0(),y,z) = 28 + 8*y + 8*z      
                        > y                   
                        = y                   
        
           if(s(x),y,z) = 20 + 4*x + 8*y + 8*z
                        > z                   
                        = z                   
        
        
        Following rules are (at-least) weakly oriented:
        

WORST_CASE(?,O(n^1))