Сложность алгоритма Маркова

[iYoung]

Здравствуйте . Проблема состоит в том , что я не могу посчитать сложность алгоритма Маркова. Есть решение задачи , но нет сложности . Цену за Вашу помощь можно отправлять в ЛС. Заранее спасибо !

Задача - На вход под-ся слово в алфавите abcd. Необходимо в конце слова поставить знак =. Затем поставить троичное число, являющееся суммой количеств букв a и d.

Решение -

aA>Aa
bA>Ab
cA>Ac
dA>Ad
=A>A=
a=>=a
b=>=b
c=>=c
d=>=d
#a>a#
#b>b#
#c>c#
#d>d#
0A>1
1A>2
2A>A0
A>1
a@>A@a
b@>@b
c@>@c
d@>A@d
#>=@
=@>=.
a>#a
b>#b
c>#c
d>#d
.aA>Aa
bA>Ab
cA>Ac
dA>Ad
=A>A=
a=>=a
b=>=b
c=>=c
d=>=d
#a>a#
#b>b#
#c>c#
#d>d#
0A>1
1A>2
2A>A0
A>1
a@>A@a
b@>@b
c@>@c
d@>A@d
#>=@
=@>D=
0D>0.
1D>1.
2D>2.
D>0.
a>#a
b>#b
c>#c
d>#d
.