Supporting Material: Optimal detection of changepoints with a linear computational cost

considered segment variances simulated so that 95 % were within [1/10,10] and a linearly increasing number of changepoints (m = n/100). Here we also consider the cases of square root increasing changepoints (m = b√n/4c) and a fixed number of changepoints (m = 2). Both these sceanarios violate the assumptions of Theorem 3.2 from the main text. Figure 2 in the supplementary material shows the results for the varaince range [1/10,10] alongside the linearly increasing figures from the main text. Similarly, Figures 1 and 3 in the supplementary material follow the format of Figure 2 in the supplementary material repeated for ranges [1/5,5] and [1/20,20]. The results across the different ranges are similar. Firstly Figure 2(a) in the supplementary material shows that when the number of changepoints increases linearly with n, PELT does indeed have a CPU cost that is linear in n. By comparison Figures 2(b) and 2(c) in the supplementary material show that if the number of changepoints increases at a slower rate, the CPU cost of PELT is no longer linear. However even in the latter two cases, substantial computational 1 savings are attained relative to optimal partitioning. Figures 2(g)-2(i) in the supplementary material show the increase in accuracy in terms of mean square error of estimates of the parameter. For the fixed number of changepoints scenario the difference is negligible but, for the linearly increasing number of changepoints scenario, the difference is relatively large. Figures 4(a)-4(i) in the supplementary material show the proportion of correctly iden-tified changepoints against the number of falsely detected changepoints. The fixed number of changepoints has the highest detection rate for the fewest falsely detected changepoints. This decreases as the number of changepoints increases through square root to linear increases. In all examples PELT has, for the smaller false detection rates, a higher correct detection rate than Binary Segmentation. Figure 5 compares the timings of the Binary Segmentation algorithm with PELT. In all examples, Binary Segmentation is computationally quicker