# Computing Maximal Lyndon Substrings of a String
## 5 Data and Measurements  
Initially, computations were performed on the Department of Computing and Software's _moore_ server; memory: 32 GB (DDR4 @ 2400 MHz), CPU: 8 \(\times\) Intel Xeon E5-2687W v4 @ 3.00 GHz, OS: Linux Version 2.6.18-419.el5 (gcc Version 4.1.2 and Red Hat Version 4.1.2-55). To verify correctness, new randomized data were produced and computed independently on the University of Toronto Mississauga's _octolab_ cluster; memory: 8 \(\times\) 32 GB (DDR4 @ 3200 MHz), CPU: 8 \(\times\) AMD Ryzen Threadripper 1920X (12-Core) @ 4.00 GHz, OS: Ubuntu 16.04.6 LTS (gcc Version 5.4.0). The results of both were extremely similar, and those reported herein are those generated using the _moore_ server. All the programs were compiled without any additional level of optimization (i.e., neither -01, nor -02, nor -03 flags were specified for the compilation). The CPU time was measured in clock ticks with 1,000,000 clock ticks per second. Since the execution time was negligible for short strings, the processing of the same string was repeated several times (the repeat factor varied from \(10^{6}\), for strings of length 10, to one, for strings of length \(5\times 10^{6}\)), resulting in a higher precision. Thus, for graphing, the logarithmic scale was used for both, \(x\)-axis representing the length of the strings and \(y\)-axis representing the time. We used four categories of randomly generated datasets:  
1. bin random strings over an integer alphabet with exactly two distinct letters (kind of binary strings).
2. dna random strings over an integer alphabet with exactly four distinct letters (kind of random DNA strings).
3. eng random strings over an integer alphabet with exactly 26 distinct letters (kind of random English).
4. int random strings over an integer alphabet (i.e., over the alphabet \(\{0,...,n-1\}\)).  
Each dataset contains 100 randomly generated strings of the same length. For each category, there were datasets for length s 10, 50, \(10^{2}\), \(5\times 10^{2}\),..., \(10^{5}\), \(5\times 10^{5}\), \(10^{6}\), and \(5\times 10^{6}\). The minimum, average, and maximum times for each dataset were computed. Since the variance for each dataset was minimal, the results for minimum times and the results for maximum times completely mimicked the results for the average times, so we only present the averages here.  
Tables 1-4 and the graphs in Figures 7-10 from Section 7 clearly indicate that the performance of the three algorithms is linear and virtually indistinguishable. We expected _IDLA_ and _TRLA_ to exhibit linear behaviour on random strings as such strings tend to have many, but short right-maximal Lyndon substrings. However, we did not expect the results to be so close.  
Despite the fact that _IDLA_ performed in linear time on the random strings, it is relatively easy to force it into its worst quadratic performance. The dataset extreme_idla contains individual strings \(0123...n-1\) of the required lengths. Table 5 and the graph in Figure 11 from Section 7 show this clearly.  
In Section 3.5, we describe how the three datasets, extreme_trla, extreme_trla1, and extreme_trla2, are generated and why. The results of experimenting with these datasets do not suggest that the worst-case complexity for _TRLA_ is \(\mathcal{O}(n\ \log(n))\). Yet again, the performances of the three algorithms are linear and virtually indistinguishable; see Tables 6-8 and the graphs in Figures 12-14 in Section 7.