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:

0(1(1(x1))) → 1(2(1(2(0(x1)))))
0(3(1(x1))) → 1(3(2(2(0(x1)))))
0(3(1(x1))) → 3(2(1(2(0(x1)))))
0(3(1(x1))) → 1(3(3(3(2(0(x1))))))
0(4(1(x1))) → 2(1(2(0(4(x1)))))
0(0(4(5(x1)))) → 0(0(2(5(4(x1)))))
0(1(4(1(x1)))) → 0(1(2(2(4(1(x1))))))
0(1(4(5(x1)))) → 4(0(1(2(5(4(x1))))))
0(1(5(1(x1)))) → 1(2(2(5(0(1(x1))))))
0(1(5(3(x1)))) → 0(5(3(2(1(x1)))))
0(2(4(1(x1)))) → 1(3(3(2(0(4(x1))))))
0(2(4(1(x1)))) → 4(2(1(2(0(4(x1))))))
0(2(4(5(x1)))) → 0(2(2(5(0(4(x1))))))
0(3(1(5(x1)))) → 0(1(2(5(3(x1)))))
0(3(1(5(x1)))) → 1(2(5(3(0(4(x1))))))
0(3(5(1(x1)))) → 1(2(5(3(0(x1)))))
0(3(5(1(x1)))) → 0(5(2(1(2(3(x1))))))
0(3(5(5(x1)))) → 0(3(2(5(5(x1)))))
0(4(0(1(x1)))) → 2(0(4(4(0(1(x1))))))
0(4(1(5(x1)))) → 1(2(5(0(4(x1)))))
0(4(3(5(x1)))) → 0(4(3(2(5(4(x1))))))
0(4(5(1(x1)))) → 2(5(4(4(0(1(x1))))))
3(0(1(5(x1)))) → 3(1(4(0(5(4(x1))))))
3(0(3(1(x1)))) → 1(3(3(2(0(x1)))))
3(0(3(5(x1)))) → 3(2(5(0(2(3(x1))))))
3(3(0(1(x1)))) → 0(1(3(2(2(3(x1))))))
3(4(5(1(x1)))) → 3(2(5(4(2(1(x1))))))
4(1(3(5(x1)))) → 1(2(5(3(4(4(x1))))))
4(1(5(1(x1)))) → 4(4(5(1(2(1(x1))))))
4(4(1(5(x1)))) → 4(1(2(5(4(x1)))))
0(1(4(5(5(x1))))) → 0(5(1(4(2(5(x1))))))
0(2(1(4(5(x1))))) → 0(0(1(2(5(4(x1))))))
0(2(1(5(5(x1))))) → 0(1(2(2(5(5(x1))))))
0(4(2(4(1(x1))))) → 1(3(2(0(4(4(x1))))))
0(4(5(4(3(x1))))) → 2(5(0(4(4(3(x1))))))
0(5(1(5(1(x1))))) → 0(5(1(1(2(5(x1))))))
0(5(2(1(5(x1))))) → 1(2(5(5(0(4(x1))))))
0(5(2(4(1(x1))))) → 4(5(2(1(2(0(x1))))))
3(0(1(4(1(x1))))) → 0(4(4(1(3(1(x1))))))
3(0(1(4(1(x1))))) → 4(3(2(0(1(1(x1))))))
3(0(3(5(5(x1))))) → 3(3(2(5(0(5(x1))))))
3(0(5(3(1(x1))))) → 1(0(3(3(2(5(x1))))))
4(0(1(4(1(x1))))) → 4(4(0(1(3(1(x1))))))
4(0(1(5(1(x1))))) → 0(1(2(5(4(1(x1))))))
4(0(2(4(5(x1))))) → 4(0(2(5(0(4(x1))))))
4(1(1(5(1(x1))))) → 1(1(2(5(4(1(x1))))))
4(5(1(4(1(x1))))) → 4(4(1(2(1(5(x1))))))
4(5(2(3(1(x1))))) → 4(3(1(2(2(5(x1))))))
4(5(4(3(1(x1))))) → 4(1(2(5(3(4(x1))))))
4(5(5(3(1(x1))))) → 1(3(2(5(5(4(x1))))))

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 2.
The certificate found is represented by the following graph.

Start state: 5344
Accept states: [5345, 5346, 5347]
Transitions:
5344→5345[0_1|0]
5344→5346[3_1|0]
5344→5347[4_1|0]
5344→5344[1_1|0, 2_1|0, 5_1|0]
5344→5348[0_1|1]
5344→5352[1_1|1]
5344→5357[1_1|1]
5344→5362[5_1|1]
5344→5367[1_1|1]
5344→5372[4_1|1]
5344→5377[5_1|1]
5344→5382[1_1|1]
5344→5387[4_1|1]
5344→5391[4_1|1]
5344→5395[1_1|1]
5348→5349[2_1|1]
5349→5350[1_1|1]
5350→5351[2_1|1]
5351→5345[1_1|1]
5351→5348[1_1|1]
5351→5353[1_1|1]
5351→5383[1_1|1]
5352→5353[0_1|1]
5353→5354[5_1|1]
5354→5355[2_1|1]
5355→5356[2_1|1]
5356→5345[1_1|1]
5356→5348[1_1|1]
5356→5353[1_1|1]
5356→5383[1_1|1]
5357→5358[2_1|1]
5358→5359[1_1|1]
5359→5360[5_1|1]
5360→5361[4_1|1]
5361→5347[4_1|1]
5361→5372[4_1|1]
5361→5368[4_1|1]
5361→5387[4_1|1]
5361→5391[4_1|1]
5361→5396[4_1|1]
5362→5363[2_1|1]
5363→5364[1_1|1]
5364→5365[1_1|1]
5365→5366[5_1|1]
5366→5345[0_1|1]
5366→5348[0_1|1]
5367→5368[4_1|1]
5368→5369[5_1|1]
5369→5370[2_1|1]
5370→5371[1_1|1]
5370→5400[0_1|2]
5371→5347[1_1|1]
5371→5372[1_1|1]
5371→5368[1_1|1]
5371→5387[1_1|1]
5371→5391[1_1|1]
5371→5396[1_1|1]
5372→5373[0_1|1]
5373→5374[5_1|1]
5374→5375[5_1|1]
5375→5376[2_1|1]
5376→5345[1_1|1]
5376→5348[1_1|1]
5377→5378[5_1|1]
5378→5379[2_1|1]
5379→5380[2_1|1]
5380→5381[1_1|1]
5381→5345[0_1|1]
5381→5348[0_1|1]
5382→5383[0_1|1]
5383→5384[4_1|1]
5384→5385[4_1|1]
5385→5386[5_1|1]
5386→5373[2_1|1]
5386→5388[2_1|1]
5386→5392[2_1|1]
5387→5388[0_1|1]
5388→5389[2_1|1]
5389→5390[1_1|1]
5390→5373[2_1|1]
5390→5388[2_1|1]
5390→5392[2_1|1]
5391→5392[0_1|1]
5392→5393[5_1|1]
5393→5394[2_1|1]
5394→5373[1_1|1]
5394→5388[1_1|1]
5394→5392[1_1|1]
5395→5396[4_1|1]
5396→5397[5_1|1]
5397→5398[2_1|1]
5398→5399[1_1|1]
5399→5384[0_1|1]
5400→5401[2_1|2]
5401→5402[1_1|2]
5402→5403[2_1|2]
5403→5373[1_1|2]
5403→5388[1_1|2]
5403→5392[1_1|2]

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