The brute-forceforward–backward procedurealgorithm forruns thewith solutiontime ofcomplexity this<math> problemO(S isT) the</math> generationin ofspace all<math> possibleO(S T) </math>, where <math>N^T</math> stateis sequencesthe andlength calculatingof the jointtime probabilitysequence ofand each<math>S</math> stateis sequencethe withnumber theof observedsymbols seriesin ofthe eventsstate alphabet. The Thisalgorithm approachcan hasalso run in constant space with [[time complexity]] <math> O(TS \cdot N^T^2) </math>,whereby recomputing values at each step.<mathref>T[[#RussellNorvig10|Russell & Norvig 2010 pp. 575]]</mathref> isFor thecomparison, lengtha ofbrute-force sequencesprocedure andwould generate all possible <math>NS^T</math> isstate sequences and calculate the numberjoint probability of symbolseach instate sequence with the stateobserved alphabetseries of events, which would have [[time complexity]] <math> O(T \cdot S^T) </math>. ThisBrute force is intractable for realistic problems, as the number of possible hidden node sequences typically is extremely high. However, the forward–backward algorithm has time complexity <math> O(N^2 T)\, </math>.
An enhancement to the general forward-backward algorithm, called the [[Island algorithm]], trades smaller memory usage for longer running time, taking <math> O(N^2S T \log T)\, </math> time and <math> O(NS \log T)\, </math> memory. On a computer with an unlimited number of processors, this can be reduced to <math> O(N^2 T)\, </math> total time, while still taking only <math> O(N \log T)\, </math> memory.<ref>J. Binder, K. Murphy and S. Russell. Space-Efficient Inference in Dynamic Probabilistic Networks. Int'l, Joint Conf. on Artificial Intelligence, 1997.</ref>
In addition, algorithms have been developed to compute <math>\mathbf{f_{0:t+1}}</math> efficiently through online smoothing such as the fixed-lag smoothing (FLS) algorithm.<ref>[[#RussellNorvig10|Russell & Norvig 2010 Figure 15.6 pp. 580]].</ref>
