The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(1, n^1).

(0) Obligation:

Runtime Complexity TRS:
The TRS R consists of the following rules:

f(f(X)) → c(n__f(n__g(n__f(X))))
c(X) → d(activate(X))
h(X) → c(n__d(X))
f(X) → n__f(X)
g(X) → n__g(X)
d(X) → n__d(X)
activate(n__f(X)) → f(activate(X))
activate(n__g(X)) → g(X)
activate(n__d(X)) → d(X)
activate(X) → X

Rewrite Strategy: INNERMOST

(1) CpxTrsMatchBoundsProof (EQUIVALENT transformation)

A linear upper bound on the runtime complexity of the TRS R could be shown with a Match Bound [MATCHBOUNDS1,MATCHBOUNDS2] of 4.
The certificate found is represented by the following graph.

Start state: 1
Accept states: [2]
Transitions:
1→2[f_1|0, c_1|0, h_1|0, g_1|0, d_1|0, activate_1|0, n__f_1|1, n__g_1|1, n__d_1|1, g_1|1, d_1|1, n__g_1|2, n__d_1|2]
1→3[d_1|1, n__d_1|2]
1→4[c_1|1]
1→5[f_1|1, n__f_1|2]
1→6[d_1|2, n__d_1|3]
1→7[c_1|2]
1→10[d_1|3, n__d_1|4]
2→2[n__f_1|0, n__g_1|0, n__d_1|0]
3→2[activate_1|1, n__f_1|1, g_1|1, n__g_1|1, d_1|1, n__d_1|1, n__g_1|2, n__d_1|2]
3→5[f_1|1, n__f_1|2]
3→7[c_1|2]
3→10[d_1|3, n__d_1|4]
4→2[n__d_1|1]
5→2[activate_1|1, n__f_1|1, g_1|1, n__g_1|1, d_1|1, n__d_1|1, n__g_1|2, n__d_1|2]
5→5[f_1|1, n__f_1|2]
5→7[c_1|2]
5→10[d_1|3, n__d_1|4]
6→4[activate_1|2]
6→2[d_1|2, n__d_1|2, n__d_1|3]
7→8[n__f_1|2]
8→9[n__g_1|2]
9→5[n__f_1|2]
10→7[activate_1|3]
10→11[f_1|3, n__f_1|4]
10→8[n__f_1|3]
11→8[activate_1|3]
11→9[g_1|3, n__g_1|3, n__g_1|4]

(2) BOUNDS(1, n^1)