In this section, we will compare the computational complexity of the previous algorithm and the proposed algorithm. For the comparison, we will set the unit operation to be a polynomial multiplication. In the previous algorithm, for a given puncturing pattern, we have to solve
l,
K(
N−
n)≤
l≤
K(
N−1) independent equations, each having
K
2 unknowns. Finding the bases of the solution space with Gaussian elimination for a linear system in
K
2 unknowns will require
O(
K
6) polynomial operations, since the complexity of solving the linear system in
K
2 unknowns is the same as the complexity of finding inverse matrix of
K
2×
K
2 matrix in big-
O notation. In the proposed algorithm, the linear systems we have to solve is given in (
15). We can solve (
15) by simple Gauss elimination. It is not difficult to see that solving (
15) requires at most
n matrix inversions and
n
2+2
n matrix multiplications of
\(S_{r}^{(j)}(Z)\)’s. Note that
\(S_{r}^{(j)}(Z)\)’s are polynomials of
Z given in (
7). Due to the structural property of
Z
l
, the inversions and multiplications of
\(S_{r}^{(j)}(Z)\) requires only the computations of their first rows. Thus, the computational complexity of these
K×
K matrices
\(S_{r}^{(j)}(Z)\)’s is not
O(
K
3) but
O(
K
2). Therefore the overall complexity of the proposed algorithm is
O(
K
2
n
2)≈
O(
K
4). The remaining issue of analysis is that is the validity of setting a polynomial operation as unit operation, since the complexity of the polynomial operation(meaning the multiplication of two polynomials) is dependent on the degrees of the polynomials. In [
4], the polynomials of interest are the entries of
G(
D), whereas the polynomials of interest in the proposed algorithm are the entries of the first row of
\(S_{r}^{(j)}(Z)\), which are the polynomials in
H(
D). It is very difficult to estimate the degrees of the polynomials in
H(
D) from these in
G(
D). The maximal degree of the polynomials in
H(
D) can be either greater or less than that of the polynomials in
G(
D). Our complexity comparison is based on the assumption that both degrees are almost the same. In our example 2, both degrees are the same as 2. It can be easily shown that the maximal degree of the polynomials in
H(
D) is at most
K times that of the polynomials in
G(
D). Even in this worst case, the computational complexity of our proposed algorithm is no more than
O(
K
6), the complexity of the algorithm in [
4].