WORST_CASE(?,O(n^1))
* Step 1: NaturalMI 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:
        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(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) = [1] x1 + [1] x2 + [4]         
                 p(Nil) = [4]                           
            p(comp_f_g) = [1] x1 + [1] x2 + [8]         
          p(comp_f_g#1) = [1] x1 + [1] x2 + [1] x3 + [0]
                p(main) = [6] x1 + [3]                  
              p(walk#1) = [4] x1 + [2]                  
             p(walk_xs) = [14]                          
           p(walk_xs_3) = [1] x1 + [3]                  
        
        Following rules are strictly oriented:
        comp_f_g#1(comp_f_g(x7,x9),walk_xs_3(x8),x12) = [1] x12 + [1] x7 + [1] x8 + [1] x9 + [11] 
                                                      > [1] x12 + [1] x7 + [1] x8 + [1] x9 + [4]  
                                                      = comp_f_g#1(x7,x9,Cons(x8,x12))            
        
              comp_f_g#1(walk_xs(),walk_xs_3(x8),x12) = [1] x12 + [1] x8 + [17]                   
                                                      > [1] x12 + [1] x8 + [4]                    
                                                      = Cons(x8,x12)                              
        
                                    main(Cons(x4,x5)) = [6] x4 + [6] x5 + [27]                    
                                                      > [1] x4 + [4] x5 + [9]                     
                                                      = comp_f_g#1(walk#1(x5),walk_xs_3(x4),Nil())
        
                                          main(Nil()) = [27]                                      
                                                      > [4]                                       
                                                      = Nil()                                     
        
                                  walk#1(Cons(x4,x3)) = [4] x3 + [4] x4 + [18]                    
                                                      > [4] x3 + [1] x4 + [13]                    
                                                      = comp_f_g(walk#1(x3),walk_xs_3(x4))        
        
                                        walk#1(Nil()) = [18]                                      
                                                      > [14]                                      
                                                      = walk_xs()                                 
        
        
        Following rules are (at-least) weakly oriented:
        

WORST_CASE(?,O(n^1))