# A Multithreaded Algorithm for the Computation of Sample Entropy
## 6 Discussion  
The efficiency of the computation of sample entropy depends on several factors. The most important one is the size of the time series since the complexity of the problem is relatively high: \(O(n^{2})\). For a short recording, the computational time is not significant, but for a larger signal, for example, for a 24 h Holter recording, this time is not an amount which could be easily ignored, especially when more than one signal is to be processed or more than single values of \(m\) and \(r\) are to be investigated for each recording. Even though the typical values \(m=2\), \(r=0.2\) are almost always used, investigation of different values for those parameters requires additional executions. The values of the parameters \(m\) and \(r\) both affect the execution time. The larger the size of the embedding space \(m\), the larger the size of the vectors checked for similarity in each step. This is, however, a linear dependency. If we select to reflect the influence of \(m\) in the computational complexity, the complexity of the algorithm becomes \(O(mn^{2})\), with \(m\ll n\). Execution time also depends on the threshold distance \(r\). Since, according to the definition of sample entropy, the maximum (infinity) norm, i.e., \(||x||_{\infty}=max(|x_{1}|,\ldots,|x_{n}|)\), is used for the similarity checks, the similarity can sometimes be decided early, even during the comparison of the first elements of the two vectors. In this case, the comparisons of the rest of the elements of the two vectors are not necessary (see lines 3 and 4 of the straightforward implementation in Section 5). The smaller the value of \(r\), the larger the probability that a similarity check can be decided early and the smaller the average amount of time necessary for a similarity check. Faster algorithms can be achieved in two ways. The first one is to design algorithms which compute an approximation of the final result. Especially in approximate and sample entropy computation, which by definition are estimations of the entropy of the system, this approximation does not necessarily significantly affect the discriminating power of each method. However, such an approach should be considered as a limitation from the algorithmic point of view. Such limitation does not exist for the bucket-assisted algorithm since it computes the exact value of sample entropy, returning exactly the same result of the straightforward implementation and according to the definition. Thus, no remarkable limitations of the bucket-assisted algorithm should be mentioned. Figure 2: **Left panel**: speedups for randomly generated time series. **Right panel**: speedups for a set of 54 Holter recordings in sinus rhythm. As a drawback, the complexity of the implementation can be considered. Not the algorithmic one, which is still \(O(n^{2})\), but the development effort and the complicated data structures and nested loops required for the implementation. Even though this is not a problem per se, recent compiler technology targets simple structures and uniform loops for speeding up applications and automatic extraction of parallelism. As we claimed in [13], the bucket-assisted algorithm is much faster than other similar algorithms. However, due to the implementation complexity, the bucket-assisted algorithm cannot expect to gain as much as the simpler implementations from future achievements in compiler and automatic code parallelization technology. In this work, we proposed parallel implementations for the bucket-assisted algorithm, tested on common cost-effective home processors, employing multithreading technology. We performed experiments with (a) randomly generated time series and (b) 54 Holter recordings, approximately 24 h long each. We first compared the performance of the bucket-assisted algorithm compared to a straightforward implementation based on the definition of sample entropy.