WORST_CASE(?,O(n^1))
* Step 1: NaturalPI WORST_CASE(?,O(n^1))
    + Considered Problem:
        - Strict TRS:
            comp_f_g#1(comp_f_g(x7,x9),walk_xs_3(x8),x12) -> comp_f_g#1(x7,x9,Cons(x8,x12))
            comp_f_g#1(walk_xs(),walk_xs_3(x8),x12) -> Cons(x8,x12)
            main(Cons(x4,x5)) -> comp_f_g#1(walk#1(x5),walk_xs_3(x4),Nil())
            main(Nil()) -> Nil()
            walk#1(Cons(x4,x3)) -> comp_f_g(walk#1(x3),walk_xs_3(x4))
            walk#1(Nil()) -> walk_xs()
        - Signature:
            {comp_f_g#1/3,main/1,walk#1/1} / {Cons/2,Nil/0,comp_f_g/2,walk_xs/0,walk_xs_3/1}
        - Obligation:
            innermost runtime complexity wrt. defined symbols {comp_f_g#1,main,walk#1} and constructors {Cons,Nil
            ,comp_f_g,walk_xs,walk_xs_3}
    + 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(comp_f_g) = {1},
          uargs(comp_f_g#1) = {1}
        
        Following symbols are considered usable:
          {comp_f_g#1,main,walk#1}
        TcT has computed the following interpretation:
                p(Cons) = 4 + x2     
                 p(Nil) = 2          
            p(comp_f_g) = 8 + x1 + x2
          p(comp_f_g#1) = 5 + x1 + x3
                p(main) = 4 + 6*x1   
              p(walk#1) = 1 + 5*x1   
             p(walk_xs) = 7          
           p(walk_xs_3) = 8          
        
        Following rules are strictly oriented:
        comp_f_g#1(comp_f_g(x7,x9),walk_xs_3(x8),x12) = 13 + x12 + x7 + x9                        
                                                      > 9 + x12 + x7                              
                                                      = comp_f_g#1(x7,x9,Cons(x8,x12))            
        
              comp_f_g#1(walk_xs(),walk_xs_3(x8),x12) = 12 + x12                                  
                                                      > 4 + x12                                   
                                                      = Cons(x8,x12)                              
        
                                    main(Cons(x4,x5)) = 28 + 6*x5                                 
                                                      > 8 + 5*x5                                  
                                                      = comp_f_g#1(walk#1(x5),walk_xs_3(x4),Nil())
        
                                          main(Nil()) = 16                                        
                                                      > 2                                         
                                                      = Nil()                                     
        
                                  walk#1(Cons(x4,x3)) = 21 + 5*x3                                 
                                                      > 17 + 5*x3                                 
                                                      = comp_f_g(walk#1(x3),walk_xs_3(x4))        
        
                                        walk#1(Nil()) = 11                                        
                                                      > 7                                         
                                                      = walk_xs()                                 
        
        
        Following rules are (at-least) weakly oriented:
        

WORST_CASE(?,O(n^1))