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

(0) Obligation:

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

active(c) → mark(f(g(c)))
active(f(g(X))) → mark(g(X))
proper(c) → ok(c)
proper(f(X)) → f(proper(X))
proper(g(X)) → g(proper(X))
f(ok(X)) → ok(f(X))
g(ok(X)) → ok(g(X))
top(mark(X)) → top(proper(X))
top(ok(X)) → top(active(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 6.
The certificate found is represented by the following graph.

Start state: 2608
Accept states: [2609]
Transitions:
2608→2609[active_1|0, proper_1|0, f_1|0, g_1|0, top_1|0]
2608→2610[mark_1|1]
2608→2613[ok_1|1]
2608→2614[ok_1|1]
2608→2615[ok_1|1]
2608→2616[top_1|1]
2608→2617[top_1|1]
2608→2618[top_1|2]
2608→2619[top_1|2]
2608→2624[top_1|3]
2608→2632[top_1|3]
2608→2636[top_1|4]
2608→2637[top_1|4]
2608→2640[top_1|5]
2608→2642[top_1|5]
2608→2645[top_1|6]
2609→2609[c|0, mark_1|0, ok_1|0]
2610→2611[f_1|1]
2611→2612[g_1|1]
2612→2609[c|1]
2613→2609[c|1]
2614→2609[f_1|1]
2614→2614[ok_1|1]
2615→2609[g_1|1]
2615→2615[ok_1|1]
2616→2609[proper_1|1]
2616→2613[ok_1|1]
2617→2609[active_1|1]
2617→2610[mark_1|1]
2618→2613[active_1|2]
2618→2620[mark_1|2]
2619→2610[proper_1|2]
2619→2623[f_1|2]
2619→2630[ok_1|3]
2620→2621[f_1|2]
2621→2622[g_1|2]
2622→2609[c|2]
2623→2611[proper_1|2]
2623→2625[g_1|2]
2623→2628[ok_1|3]
2624→2620[proper_1|3]
2624→2626[f_1|3]
2624→2634[ok_1|4]
2625→2612[proper_1|2]
2625→2627[ok_1|2]
2626→2621[proper_1|3]
2626→2629[g_1|3]
2626→2633[ok_1|4]
2627→2609[c|2]
2628→2627[g_1|3]
2629→2622[proper_1|3]
2629→2631[ok_1|3]
2630→2628[f_1|3]
2631→2609[c|3]
2632→2630[active_1|3]
2632→2635[mark_1|4]
2633→2631[g_1|4]
2634→2633[f_1|4]
2635→2627[g_1|4]
2636→2634[active_1|4]
2636→2638[mark_1|5]
2637→2635[proper_1|4]
2637→2639[g_1|5]
2637→2633[ok_1|4]
2638→2631[g_1|5]
2639→2627[proper_1|5]
2639→2631[ok_1|3]
2640→2638[proper_1|5]
2640→2641[g_1|6]
2640→2644[ok_1|5]
2641→2631[proper_1|6]
2641→2643[ok_1|4]
2642→2633[active_1|5]
2643→2609[c|4]
2644→2643[g_1|5]
2645→2644[active_1|6]

(2) BOUNDS(O(1), O(n^1))