# Improving the Robustness of DTW to Global Time Warping Conditions in Audio Synchronization
## 4 Discussion  
In this section, we conduct two additional analyses to gain a deeper insight into our experimental results. The first analysis is to characterize the runtime of different algorithms. We can do this in two ways: a theoretical analysis and an empirical analysis. The theoretical runtime can be considered in the following manner. Let \(N\) and \(M\) represent the sequence lengths of the two sequences to be aligned, where we assume \(N\leq M\) without loss of generality. Let \(T\) represent the number of possible transition types at each location in the cost matrix. Then, the computational complexity of standard DTW is \(O(NMT)\). This applies to the seven systems that explore the use of different transition types and weights (DTW1-5, DTW1-add3, DTW1-add4) and the adaptive weighting schemes (AdaptiveWeight1-2). For the sequence length normalization methods, the computational complexity is \(O(N^{2}T)\) when downsampling and \(O(M^{2}T)\) when upsampling. For the non-uniform transition patterns, the average number of transition types per location is reduced to \(T-\Psi_{max}^{2}\), so the computational complexity is \(O(NM(T-\frac{2}{W_{max}}))\approx O(NMT)\). We used the following procedure to measure the empirical runtime. Given two sequence lengths, \(N\) and \(M\), we randomly initialize two feature matrices of size \(12\times N\) and \(12\times M\), where the 12 is selected to simulate a chroma feature representation. We begin profiling after the feature matrices have been generated, and we include feature preprocessing (e.g., downsampling for sequence length normalization), pairwise cost matrix computation, dynamic programming, backtracking, and any postprocessing (e.g., compensating for downsampling). For each setting of \((N,M)\), we repeat this process 10 times and report the average runtime. All experiments were run on a 2.1 GHz Intel Xeon processor with 192 GB of DDR4 RAM, and all alignment algorithms are implemented in cython. Figure 4 compares the runtime of all 17 alignment algorithms. Each group along the horizontal axis corresponds to one setting of \((N,M)\), where \(N\) and \(M\) indicate the lengths of the shorter and longer sequence, respectively. We have included results for \(N=1\)k, 3k, 10k, 30k, and \(M=N\), 2N, 4N. These settings allow us to see the effect of both the sequence length and the global time warp factor. For ease of viewing, the groups have been split into two subplots. Within each group, the different bars correspond to the 17 alignment algorithms; we use the same color scheme as in Figure 3. The height of each bar indicates the average runtime across 10 runs, where runtime is shown on a log scale. Note that the results for (30k, 120k) are missing for the two upsampling systems--this is because the upsampling approach creates a 120k \(\times\) 120k pairwise cost matrix and cumulative cost matrix, and this exceeded the RAM limits for our server. Figure 4: Comparison of runtimes for aligning two sequences of length \(N\) and \(M\), where \(N=1\)k, \(3\)k, \(10\)k, \(30\)k and \(M=N,2N,4N\). This selection of \((N,M)\) settings allows us to assess the effect of sequence length as well as average global time warping factor. The reported runtimes are the average of \(10\) trials. Note that the y-axis is shown on a log scale. There are several things to notice about Figure 4. First, the DTW1 through DTW5 systems have similar runtimes, since all are standard DTW with three allowable transitions. This is a baseline that represents typical DTW usage. Now, we consider the remaining groups. DTW1-add3 and DTW1-add4 (orange) have increased runtimes compared to the baseline, since they require more transition possibilities to be considered at each step of the dynamic programming stage. The sequence normalization methods (purple) have the most interesting runtime trends. When \(N\approx M\), the runtimes of all four sequence normalization methods are similar to the baseline.