text: Вычисления всех a ¯ i {\displaystyle {\bar {a}}_{i}} и c i {\displaystyle c_{i}} требуют O ( N ) {\displaystyle O(N)} действий, три преобразования Фурье требуют O ( N log ⁡ ( N ) ) {\displaystyle O(N\log(N))} действий, перемножение результатов преобразований Фурье требует O ( N ) {\displaystyle O(N)} действий, вычисление всех b i {\displaystyle b_{i}} зная значения свёртки требует O ( N ) {\displaystyle O(N)} действий.