# Exact computation cost using Forward Procedure for HMM probability evaluation

I am understanding the HMM concept for Speech Recognition. One of the three problems (HMM) to be solved is Probability evaluation $$P(O|\lambda)$$. Instead of a straightforward approach which is computationally expensive, we go for the Forward Procedure. The three steps involved in this procedure are

($$a_{ij}$$ is transition probability from state i to state j, $$b_{j}(k)$$ is observation symbol probability, and $$\pi_{i}$$ is initial state probability. There are N states.)

1. Initialization

$$\alpha_{1}(i)=\pi_{i}.b_{i}(o_{1}), 1\le i\le N.$$

1. Induction

$$\alpha_{t+1}(j)=\left[ \sum_{i=1}^{N} \alpha_{t}(i).a_{ij} \right].b_{j}(o_{t+1}),\ 1\le j\le N , \ 1\le t\le T-1$$

1. Termination

$$P(O|\lambda)=\sum_{i=1}^{N}\alpha_{T}(i)$$

The total number of multiplications is $$N.(N+1)(T-1)+N$$, which I totally get, as we have (T-1) induction equations considering every t, and in the same Induction equation we have sum of N products, and is finally multiplied with $$b_{j}(o_{t+1})$$. So far, (T-1)*(N+1). We also need to do it for every j; $$1\le j\le N$$. The final +N is to account for N multiplications needed for initializations. Hence total number of multiplications makes sense.

However, the text that I follow (Fundamentals of Speech Recognition by Rabiner) does not make sense for the total number of additions involved. The text tells me that it is $$N.(N-1).(T-1)$$. I get that, (N-1) addition operations are required to add N terms. So, for every t and j, it is obvious that total number of additions is indeed what is given.

But aren't we missing to add the additions happening in the termination step? Hence shouldn't the total number of additions be equal to $$N.(N-1).(T-1) + N-1$$ ?