WORST_CASE(Omega(n^1),O(n^1))
* Step 1: Sum WORST_CASE(Omega(n^1),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:
        Sum {left = someStrategy, right = someStrategy}
    + Details:
        ()
** Step 1.a:1: DecreasingLoops WORST_CASE(Omega(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:
        DecreasingLoops {bound = AnyLoop, narrow = 10}
    + Details:
        The system has following decreasing Loops:
          walk#1(y){y -> Cons(x,y)} =
            walk#1(Cons(x,y)) ->^+ comp_f_g(walk#1(y),walk_xs_3(x))
              = C[walk#1(y) = walk#1(y){}]

** Step 1.b: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 = Restrict, uargs = UArgs, urules = URules, selector = Just any strict-rules}
    + 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) = 11       
                 p(Nil) = 3        
            p(comp_f_g) = x1       
          p(comp_f_g#1) = 11 + 2*x1
                p(main) = 11       
              p(walk#1) = 0        
             p(walk_xs) = 0        
           p(walk_xs_3) = 1        
        
        Following rules are strictly oriented:
        main(Nil()) = 11   
                    > 3    
                    = Nil()
        
        
        Following rules are (at-least) weakly oriented:
        comp_f_g#1(comp_f_g(x7,x9),walk_xs_3(x8),x12) =  11 + 2*x7                                 
                                                      >= 11 + 2*x7                                 
                                                      =  comp_f_g#1(x7,x9,Cons(x8,x12))            
        
              comp_f_g#1(walk_xs(),walk_xs_3(x8),x12) =  11                                        
                                                      >= 11                                        
                                                      =  Cons(x8,x12)                              
        
                                    main(Cons(x4,x5)) =  11                                        
                                                      >= 11                                        
                                                      =  comp_f_g#1(walk#1(x5),walk_xs_3(x4),Nil())
        
                                  walk#1(Cons(x4,x3)) =  0                                         
                                                      >= 0                                         
                                                      =  comp_f_g(walk#1(x3),walk_xs_3(x4))        
        
                                        walk#1(Nil()) =  0                                         
                                                      >= 0                                         
                                                      =  walk_xs()                                 
        
** Step 1.b:2: 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())
            walk#1(Cons(x4,x3)) -> comp_f_g(walk#1(x3),walk_xs_3(x4))
            walk#1(Nil()) -> walk_xs()
        - Weak TRS:
            main(Nil()) -> Nil()
        - 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 = Restrict, uargs = UArgs, urules = URules, selector = Just any strict-rules}
    + 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     
                 p(Nil) = 12    
            p(comp_f_g) = x1    
          p(comp_f_g#1) = 2 + x1
                p(main) = 12    
              p(walk#1) = 2     
             p(walk_xs) = 2     
           p(walk_xs_3) = 1     
        
        Following rules are strictly oriented:
        main(Cons(x4,x5)) = 12                                        
                          > 4                                         
                          = comp_f_g#1(walk#1(x5),walk_xs_3(x4),Nil())
        
        
        Following rules are (at-least) weakly oriented:
        comp_f_g#1(comp_f_g(x7,x9),walk_xs_3(x8),x12) =  2 + x7                            
                                                      >= 2 + x7                            
                                                      =  comp_f_g#1(x7,x9,Cons(x8,x12))    
        
              comp_f_g#1(walk_xs(),walk_xs_3(x8),x12) =  4                                 
                                                      >= 4                                 
                                                      =  Cons(x8,x12)                      
        
                                          main(Nil()) =  12                                
                                                      >= 12                                
                                                      =  Nil()                             
        
                                  walk#1(Cons(x4,x3)) =  2                                 
                                                      >= 2                                 
                                                      =  comp_f_g(walk#1(x3),walk_xs_3(x4))
        
                                        walk#1(Nil()) =  2                                 
                                                      >= 2                                 
                                                      =  walk_xs()                         
        
** Step 1.b:3: 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)
            walk#1(Cons(x4,x3)) -> comp_f_g(walk#1(x3),walk_xs_3(x4))
            walk#1(Nil()) -> walk_xs()
        - Weak TRS:
            main(Cons(x4,x5)) -> comp_f_g#1(walk#1(x5),walk_xs_3(x4),Nil())
            main(Nil()) -> Nil()
        - 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 = Restrict, uargs = UArgs, urules = URules, selector = Just any strict-rules}
    + 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) = 2 
                 p(Nil) = 10
            p(comp_f_g) = x1
          p(comp_f_g#1) = x1
                p(main) = 10
              p(walk#1) = 10
             p(walk_xs) = 10
           p(walk_xs_3) = 0 
        
        Following rules are strictly oriented:
        comp_f_g#1(walk_xs(),walk_xs_3(x8),x12) = 10          
                                                > 2           
                                                = Cons(x8,x12)
        
        
        Following rules are (at-least) weakly oriented:
        comp_f_g#1(comp_f_g(x7,x9),walk_xs_3(x8),x12) =  x7                                        
                                                      >= x7                                        
                                                      =  comp_f_g#1(x7,x9,Cons(x8,x12))            
        
                                    main(Cons(x4,x5)) =  10                                        
                                                      >= 10                                        
                                                      =  comp_f_g#1(walk#1(x5),walk_xs_3(x4),Nil())
        
                                          main(Nil()) =  10                                        
                                                      >= 10                                        
                                                      =  Nil()                                     
        
                                  walk#1(Cons(x4,x3)) =  10                                        
                                                      >= 10                                        
                                                      =  comp_f_g(walk#1(x3),walk_xs_3(x4))        
        
                                        walk#1(Nil()) =  10                                        
                                                      >= 10                                        
                                                      =  walk_xs()                                 
        
** Step 1.b:4: 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))
            walk#1(Cons(x4,x3)) -> comp_f_g(walk#1(x3),walk_xs_3(x4))
            walk#1(Nil()) -> walk_xs()
        - Weak TRS:
            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()
        - 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 = Restrict, uargs = UArgs, urules = URules, selector = Just any strict-rules}
    + 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) = 0       
                 p(Nil) = 14      
            p(comp_f_g) = x1      
          p(comp_f_g#1) = 5 + 8*x1
                p(main) = 14      
              p(walk#1) = 1       
             p(walk_xs) = 0       
           p(walk_xs_3) = 1 + x1  
        
        Following rules are strictly oriented:
        walk#1(Nil()) = 1        
                      > 0        
                      = walk_xs()
        
        
        Following rules are (at-least) weakly oriented:
        comp_f_g#1(comp_f_g(x7,x9),walk_xs_3(x8),x12) =  5 + 8*x7                                  
                                                      >= 5 + 8*x7                                  
                                                      =  comp_f_g#1(x7,x9,Cons(x8,x12))            
        
              comp_f_g#1(walk_xs(),walk_xs_3(x8),x12) =  5                                         
                                                      >= 0                                         
                                                      =  Cons(x8,x12)                              
        
                                    main(Cons(x4,x5)) =  14                                        
                                                      >= 13                                        
                                                      =  comp_f_g#1(walk#1(x5),walk_xs_3(x4),Nil())
        
                                          main(Nil()) =  14                                        
                                                      >= 14                                        
                                                      =  Nil()                                     
        
                                  walk#1(Cons(x4,x3)) =  1                                         
                                                      >= 1                                         
                                                      =  comp_f_g(walk#1(x3),walk_xs_3(x4))        
        
** Step 1.b:5: 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))
            walk#1(Cons(x4,x3)) -> comp_f_g(walk#1(x3),walk_xs_3(x4))
        - Weak TRS:
            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(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 = Restrict, uargs = UArgs, urules = URules, selector = Just any strict-rules}
    + 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) = 1 + x1   
          p(comp_f_g#1) = 5*x1 + x3
                p(main) = 2 + 5*x1 
              p(walk#1) = x1       
             p(walk_xs) = 1        
           p(walk_xs_3) = x1       
        
        Following rules are strictly oriented:
        comp_f_g#1(comp_f_g(x7,x9),walk_xs_3(x8),x12) = 5 + x12 + 5*x7                    
                                                      > 4 + x12 + 5*x7                    
                                                      = comp_f_g#1(x7,x9,Cons(x8,x12))    
        
                                  walk#1(Cons(x4,x3)) = 4 + x3                            
                                                      > 1 + x3                            
                                                      = comp_f_g(walk#1(x3),walk_xs_3(x4))
        
        
        Following rules are (at-least) weakly oriented:
        comp_f_g#1(walk_xs(),walk_xs_3(x8),x12) =  5 + x12                                   
                                                >= 4 + x12                                   
                                                =  Cons(x8,x12)                              
        
                              main(Cons(x4,x5)) =  22 + 5*x5                                 
                                                >= 2 + 5*x5                                  
                                                =  comp_f_g#1(walk#1(x5),walk_xs_3(x4),Nil())
        
                                    main(Nil()) =  12                                        
                                                >= 2                                         
                                                =  Nil()                                     
        
                                  walk#1(Nil()) =  2                                         
                                                >= 1                                         
                                                =  walk_xs()                                 
        
** Step 1.b:6: EmptyProcessor WORST_CASE(?,O(1))
    + Considered Problem:
        - Weak 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:
        EmptyProcessor
    + Details:
        The problem is already closed. The intended complexity is O(1).

WORST_CASE(Omega(n^1),O(n^1))