YES(?,O(n^1))

We are left with following problem, upon which TcT provides the
certificate YES(?,O(n^1)).

Strict Trs:
  { f(X) -> n__f(X)
  , f(n__f(n__a())) -> f(n__g(n__f(n__a())))
  , a() -> n__a()
  , g(X) -> n__g(X)
  , activate(X) -> X
  , activate(n__f(X)) -> f(X)
  , activate(n__a()) -> a()
  , activate(n__g(X)) -> g(activate(X)) }
Obligation:
  innermost runtime complexity
Answer:
  YES(?,O(n^1))

We add following dependency tuples:

Strict DPs:
  { f^#(X) -> c_1()
  , f^#(n__f(n__a())) -> c_2(f^#(n__g(n__f(n__a()))))
  , a^#() -> c_3()
  , g^#(X) -> c_4()
  , activate^#(X) -> c_5()
  , activate^#(n__f(X)) -> c_6(f^#(X))
  , activate^#(n__a()) -> c_7(a^#())
  , activate^#(n__g(X)) -> c_8(g^#(activate(X)), activate^#(X)) }

and mark the set of starting terms.

We are left with following problem, upon which TcT provides the
certificate YES(?,O(n^1)).

Strict DPs:
  { f^#(X) -> c_1()
  , f^#(n__f(n__a())) -> c_2(f^#(n__g(n__f(n__a()))))
  , a^#() -> c_3()
  , g^#(X) -> c_4()
  , activate^#(X) -> c_5()
  , activate^#(n__f(X)) -> c_6(f^#(X))
  , activate^#(n__a()) -> c_7(a^#())
  , activate^#(n__g(X)) -> c_8(g^#(activate(X)), activate^#(X)) }
Weak Trs:
  { f(X) -> n__f(X)
  , f(n__f(n__a())) -> f(n__g(n__f(n__a())))
  , a() -> n__a()
  , g(X) -> n__g(X)
  , activate(X) -> X
  , activate(n__f(X)) -> f(X)
  , activate(n__a()) -> a()
  , activate(n__g(X)) -> g(activate(X)) }
Obligation:
  innermost runtime complexity
Answer:
  YES(?,O(n^1))

We estimate the number of application of {1,3,4,5} by applications
of Pre({1,3,4,5}) = {2,6,7,8}. Here rules are labeled as follows:

  DPs:
    { 1: f^#(X) -> c_1()
    , 2: f^#(n__f(n__a())) -> c_2(f^#(n__g(n__f(n__a()))))
    , 3: a^#() -> c_3()
    , 4: g^#(X) -> c_4()
    , 5: activate^#(X) -> c_5()
    , 6: activate^#(n__f(X)) -> c_6(f^#(X))
    , 7: activate^#(n__a()) -> c_7(a^#())
    , 8: activate^#(n__g(X)) -> c_8(g^#(activate(X)), activate^#(X)) }

We are left with following problem, upon which TcT provides the
certificate YES(?,O(n^1)).

Strict DPs:
  { f^#(n__f(n__a())) -> c_2(f^#(n__g(n__f(n__a()))))
  , activate^#(n__f(X)) -> c_6(f^#(X))
  , activate^#(n__a()) -> c_7(a^#())
  , activate^#(n__g(X)) -> c_8(g^#(activate(X)), activate^#(X)) }
Weak DPs:
  { f^#(X) -> c_1()
  , a^#() -> c_3()
  , g^#(X) -> c_4()
  , activate^#(X) -> c_5() }
Weak Trs:
  { f(X) -> n__f(X)
  , f(n__f(n__a())) -> f(n__g(n__f(n__a())))
  , a() -> n__a()
  , g(X) -> n__g(X)
  , activate(X) -> X
  , activate(n__f(X)) -> f(X)
  , activate(n__a()) -> a()
  , activate(n__g(X)) -> g(activate(X)) }
Obligation:
  innermost runtime complexity
Answer:
  YES(?,O(n^1))

We estimate the number of application of {1,3} by applications of
Pre({1,3}) = {2,4}. Here rules are labeled as follows:

  DPs:
    { 1: f^#(n__f(n__a())) -> c_2(f^#(n__g(n__f(n__a()))))
    , 2: activate^#(n__f(X)) -> c_6(f^#(X))
    , 3: activate^#(n__a()) -> c_7(a^#())
    , 4: activate^#(n__g(X)) -> c_8(g^#(activate(X)), activate^#(X))
    , 5: f^#(X) -> c_1()
    , 6: a^#() -> c_3()
    , 7: g^#(X) -> c_4()
    , 8: activate^#(X) -> c_5() }

We are left with following problem, upon which TcT provides the
certificate YES(?,O(n^1)).

Strict DPs:
  { activate^#(n__f(X)) -> c_6(f^#(X))
  , activate^#(n__g(X)) -> c_8(g^#(activate(X)), activate^#(X)) }
Weak DPs:
  { f^#(X) -> c_1()
  , f^#(n__f(n__a())) -> c_2(f^#(n__g(n__f(n__a()))))
  , a^#() -> c_3()
  , g^#(X) -> c_4()
  , activate^#(X) -> c_5()
  , activate^#(n__a()) -> c_7(a^#()) }
Weak Trs:
  { f(X) -> n__f(X)
  , f(n__f(n__a())) -> f(n__g(n__f(n__a())))
  , a() -> n__a()
  , g(X) -> n__g(X)
  , activate(X) -> X
  , activate(n__f(X)) -> f(X)
  , activate(n__a()) -> a()
  , activate(n__g(X)) -> g(activate(X)) }
Obligation:
  innermost runtime complexity
Answer:
  YES(?,O(n^1))

We estimate the number of application of {1} by applications of
Pre({1}) = {2}. Here rules are labeled as follows:

  DPs:
    { 1: activate^#(n__f(X)) -> c_6(f^#(X))
    , 2: activate^#(n__g(X)) -> c_8(g^#(activate(X)), activate^#(X))
    , 3: f^#(X) -> c_1()
    , 4: f^#(n__f(n__a())) -> c_2(f^#(n__g(n__f(n__a()))))
    , 5: a^#() -> c_3()
    , 6: g^#(X) -> c_4()
    , 7: activate^#(X) -> c_5()
    , 8: activate^#(n__a()) -> c_7(a^#()) }

We are left with following problem, upon which TcT provides the
certificate YES(?,O(n^1)).

Strict DPs:
  { activate^#(n__g(X)) -> c_8(g^#(activate(X)), activate^#(X)) }
Weak DPs:
  { f^#(X) -> c_1()
  , f^#(n__f(n__a())) -> c_2(f^#(n__g(n__f(n__a()))))
  , a^#() -> c_3()
  , g^#(X) -> c_4()
  , activate^#(X) -> c_5()
  , activate^#(n__f(X)) -> c_6(f^#(X))
  , activate^#(n__a()) -> c_7(a^#()) }
Weak Trs:
  { f(X) -> n__f(X)
  , f(n__f(n__a())) -> f(n__g(n__f(n__a())))
  , a() -> n__a()
  , g(X) -> n__g(X)
  , activate(X) -> X
  , activate(n__f(X)) -> f(X)
  , activate(n__a()) -> a()
  , activate(n__g(X)) -> g(activate(X)) }
Obligation:
  innermost runtime complexity
Answer:
  YES(?,O(n^1))

The following weak DPs constitute a sub-graph of the DG that is
closed under successors. The DPs are removed.

{ f^#(X) -> c_1()
, f^#(n__f(n__a())) -> c_2(f^#(n__g(n__f(n__a()))))
, a^#() -> c_3()
, g^#(X) -> c_4()
, activate^#(X) -> c_5()
, activate^#(n__f(X)) -> c_6(f^#(X))
, activate^#(n__a()) -> c_7(a^#()) }

We are left with following problem, upon which TcT provides the
certificate YES(?,O(n^1)).

Strict DPs:
  { activate^#(n__g(X)) -> c_8(g^#(activate(X)), activate^#(X)) }
Weak Trs:
  { f(X) -> n__f(X)
  , f(n__f(n__a())) -> f(n__g(n__f(n__a())))
  , a() -> n__a()
  , g(X) -> n__g(X)
  , activate(X) -> X
  , activate(n__f(X)) -> f(X)
  , activate(n__a()) -> a()
  , activate(n__g(X)) -> g(activate(X)) }
Obligation:
  innermost runtime complexity
Answer:
  YES(?,O(n^1))

Due to missing edges in the dependency-graph, the right-hand sides
of following rules could be simplified:

  { activate^#(n__g(X)) -> c_8(g^#(activate(X)), activate^#(X)) }

We are left with following problem, upon which TcT provides the
certificate YES(?,O(n^1)).

Strict DPs: { activate^#(n__g(X)) -> c_1(activate^#(X)) }
Weak Trs:
  { f(X) -> n__f(X)
  , f(n__f(n__a())) -> f(n__g(n__f(n__a())))
  , a() -> n__a()
  , g(X) -> n__g(X)
  , activate(X) -> X
  , activate(n__f(X)) -> f(X)
  , activate(n__a()) -> a()
  , activate(n__g(X)) -> g(activate(X)) }
Obligation:
  innermost runtime complexity
Answer:
  YES(?,O(n^1))

No rule is usable, rules are removed from the input problem.

We are left with following problem, upon which TcT provides the
certificate YES(?,O(n^1)).

Strict DPs: { activate^#(n__g(X)) -> c_1(activate^#(X)) }
Obligation:
  innermost runtime complexity
Answer:
  YES(?,O(n^1))

The following argument positions are usable:
  Uargs(c_1) = {1}

TcT has computed following constructor-based matrix interpretation
satisfying not(EDA).

        [n__g](x1) = [1] x1 + [3]
                                 
  [activate^#](x1) = [1] x1 + [3]
                                 
         [c_1](x1) = [1] x1 + [2]

This order satisfies following ordering constraints:

  [activate^#(n__g(X))] = [1] X + [6]         
                        > [1] X + [5]         
                        = [c_1(activate^#(X))]
                                              

Hurray, we answered YES(?,O(n^1))