# A Low-Complexity Ordered Statistics Decoding Algorithm for Short Polar Codes
## 5 Performance and Complexity Analysis
### Complexity Analysis  
In this subsection, we discuss the time and space complexity of the proposed algorithm. We begin by showing the complexity of each of the steps in the process as follows.  
1. Sorting the columns of \(G\) into descending order of absolute values of \(Y\) takes \(O(N\log N)\) time and \(O(N)\) space.
2. The Gaussian elimination process for \(G_{1}\) takes \(O(NK^{2})\) time and \(O(N)\) space. Since we are dealing with short codes, the binary addition of two length-\(N\) sequences requires only one instruction instead of \(N\) instructions. Thus, the complexity of this step simplifies to \(O(K^{2})\).
3. In the bit-flipping process, we restrict the maximum number of flipped bits to 2. Thus, the time complexity is \(O(K^{2})\) as there are \(K\) 1-bit flipping operations and \(K(K-1)/2\) 2-bit flipping operations at most with each flipping operation needing \(O(1)\) time to compute the \(f\) value of the new codeword. The space complexity is \(O(1)\) since we only need to store the flipped positions of current most likely codeword and its \(f\) value.  
To summarize, TH-OSD requires \(O(NK^{2})\) time and \(O(N)\) space in total. The time complexity can be simplified to \(O(K^{2})\) for small N. As a comparison, the SC decoding algorithm has a time and space complexities both equal to \(O(N\log N)\). SCL has a time complexity \(O(LN\log N)\) and a space complexity \(O(LN)\)[2]. Step 3 is the largest contributor to the time complexity, especially when the SNR is low. We can reduce the decoding complexity by reducing the number of tested codewords, which is TH-OSD's intent.  
When the SNR increases, the number of tested codewords decreases. The main source of complexity is the matrix diagonalization, which is \(O(K^{2})\), as discussed above. More specifically, the diagonalization operation in Step 2 requires \(K^{2}\) additions. The SC decoding algorithm performs \(N\log N\) hyperbolic tangent (tanh) operations, \(\frac{1}{2}N\log N\) inverse hyperbolic tangent (atanh) operations, \(\frac{1}{2}N\log N\) multiplication operations, and \(\frac{1}{2}N\log N\) addition operations. (We present the complexity analysis of the SC algorithm in Appendix C). If a tanh or atanh operation requires \(CT\) time, where \(T\) is the time needed for an addition operation and \(C\) is the ratio of the time needed for a tanh/atanh operation to the time needed for an addition operation, then the total time consumed by SC would be \(\mathrm{T}_{SC}(N)=\left(\frac{3}{2}C+1\right)N\log NT\) compared with TH-OSD's \(\mathrm{T}_{TH-OSD}(N)=K^{2}T\). We know that hyperbolic functions are expensive compared to binary additions. Thus, \(C>1\). If \(N\) and \(K\) are small, \(\mathrm{T}_{TH-OSD}(N)\) is usually less than \(\mathrm{T}_{SC}(N)\). For example, using \(N=64,K=32\), results in \(\mathrm{T}_{TH-OSD}(N)\leq\mathrm{T}_{SC}(N)\). Thus, TH-OSD is faster than SC in high SNR scenarios for short codes. As block length becomes longer (e.g., \(N\geq 1024\)), TH-OSD will gradually lose its speed advantage over SC. Thus, TH-OSD is suitable for short codes.