WORST_CASE(?,O(n^1))
* Step 1: NaturalMI WORST_CASE(?,O(n^1))
    + Considered Problem:
        - Strict TRS:
            f(x,Cons(x',xs)) -> f[Ite][False][Ite](lt0(x,Cons(Nil(),Nil())),x,Cons(x',xs))
            f(x,Nil()) -> Cons(Nil(),Cons(Nil(),Cons(Nil(),Cons(Nil(),Nil()))))
            g(x,Cons(x',xs)) -> g[Ite][False][Ite](lt0(x,Cons(Nil(),Nil())),x,Cons(x',xs))
            g(x,Nil()) -> Cons(Nil(),Cons(Nil(),Cons(Nil(),Cons(Nil(),Nil()))))
            goal(x,y) -> Cons(f(x,y),Cons(g(x,y),Nil()))
            lt0(x,Nil()) -> False()
            lt0(Cons(x',xs'),Cons(x,xs)) -> lt0(xs',xs)
            lt0(Nil(),Cons(x',xs)) -> True()
            notEmpty(Cons(x,xs)) -> True()
            notEmpty(Nil()) -> False()
            number4(n) -> Cons(Nil(),Cons(Nil(),Cons(Nil(),Cons(Nil(),Nil()))))
        - Weak TRS:
            f[Ite][False][Ite](False(),Cons(x,xs),y) -> f(xs,Cons(Cons(Nil(),Nil()),y))
            f[Ite][False][Ite](True(),x',Cons(x,xs)) -> f(x',xs)
            g[Ite][False][Ite](False(),Cons(x,xs),y) -> g(xs,Cons(Cons(Nil(),Nil()),y))
            g[Ite][False][Ite](True(),x',Cons(x,xs)) -> g(x',xs)
        - Signature:
            {f/2,f[Ite][False][Ite]/3,g/2,g[Ite][False][Ite]/3,goal/2,lt0/2,notEmpty/1,number4/1} / {Cons/2,False/0
            ,Nil/0,True/0}
        - Obligation:
            innermost runtime complexity wrt. defined symbols {f,f[Ite][False][Ite],g,g[Ite][False][Ite],goal,lt0
            ,notEmpty,number4} and constructors {Cons,False,Nil,True}
    + 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(Cons) = {1,2},
          uargs(f[Ite][False][Ite]) = {1},
          uargs(g[Ite][False][Ite]) = {1}
        
        Following symbols are considered usable:
          {f,f[Ite][False][Ite],g,g[Ite][False][Ite],goal,lt0,notEmpty,number4}
        TcT has computed the following interpretation:
                        p(Cons) = [1] x1 + [1] x2 + [1]         
                       p(False) = [3]                           
                         p(Nil) = [0]                           
                        p(True) = [4]                           
                           p(f) = [7] x1 + [2] x2 + [6]         
          p(f[Ite][False][Ite]) = [1] x1 + [7] x2 + [2] x3 + [0]
                           p(g) = [8] x1 + [2] x2 + [6]         
          p(g[Ite][False][Ite]) = [1] x1 + [8] x2 + [2] x3 + [0]
                        p(goal) = [15] x1 + [8] x2 + [15]       
                         p(lt0) = [1] x2 + [4]                  
                    p(notEmpty) = [10] x1 + [10]                
                     p(number4) = [1] x1 + [6]                  
        
        Following rules are strictly oriented:
                    f(x,Cons(x',xs)) = [7] x + [2] x' + [2] xs + [8]                             
                                     > [7] x + [2] x' + [2] xs + [7]                             
                                     = f[Ite][False][Ite](lt0(x,Cons(Nil(),Nil())),x,Cons(x',xs))
        
                          f(x,Nil()) = [7] x + [6]                                               
                                     > [4]                                                       
                                     = Cons(Nil(),Cons(Nil(),Cons(Nil(),Cons(Nil(),Nil()))))     
        
                    g(x,Cons(x',xs)) = [8] x + [2] x' + [2] xs + [8]                             
                                     > [8] x + [2] x' + [2] xs + [7]                             
                                     = g[Ite][False][Ite](lt0(x,Cons(Nil(),Nil())),x,Cons(x',xs))
        
                          g(x,Nil()) = [8] x + [6]                                               
                                     > [4]                                                       
                                     = Cons(Nil(),Cons(Nil(),Cons(Nil(),Cons(Nil(),Nil()))))     
        
                           goal(x,y) = [15] x + [8] y + [15]                                     
                                     > [15] x + [4] y + [14]                                     
                                     = Cons(f(x,y),Cons(g(x,y),Nil()))                           
        
                        lt0(x,Nil()) = [4]                                                       
                                     > [3]                                                       
                                     = False()                                                   
        
        lt0(Cons(x',xs'),Cons(x,xs)) = [1] x + [1] xs + [5]                                      
                                     > [1] xs + [4]                                              
                                     = lt0(xs',xs)                                               
        
              lt0(Nil(),Cons(x',xs)) = [1] x' + [1] xs + [5]                                     
                                     > [4]                                                       
                                     = True()                                                    
        
                notEmpty(Cons(x,xs)) = [10] x + [10] xs + [20]                                   
                                     > [4]                                                       
                                     = True()                                                    
        
                     notEmpty(Nil()) = [10]                                                      
                                     > [3]                                                       
                                     = False()                                                   
        
                          number4(n) = [1] n + [6]                                               
                                     > [4]                                                       
                                     = Cons(Nil(),Cons(Nil(),Cons(Nil(),Cons(Nil(),Nil()))))     
        
        
        Following rules are (at-least) weakly oriented:
        f[Ite][False][Ite](False(),Cons(x,xs),y) =  [7] x + [7] xs + [2] y + [10]  
                                                 >= [7] xs + [2] y + [10]          
                                                 =  f(xs,Cons(Cons(Nil(),Nil()),y))
        
        f[Ite][False][Ite](True(),x',Cons(x,xs)) =  [2] x + [7] x' + [2] xs + [6]  
                                                 >= [7] x' + [2] xs + [6]          
                                                 =  f(x',xs)                       
        
        g[Ite][False][Ite](False(),Cons(x,xs),y) =  [8] x + [8] xs + [2] y + [11]  
                                                 >= [8] xs + [2] y + [10]          
                                                 =  g(xs,Cons(Cons(Nil(),Nil()),y))
        
        g[Ite][False][Ite](True(),x',Cons(x,xs)) =  [2] x + [8] x' + [2] xs + [6]  
                                                 >= [8] x' + [2] xs + [6]          
                                                 =  g(x',xs)                       
        

WORST_CASE(?,O(n^1))