  In recent years, various means of efficiently detecting changepoints in the
univariate setting have been proposed, with one popular approach involving
minimising a penalised cost function using dynamic programming. In some
situations, these algorithms can have an expected computational cost that is
linear in the number of data points; however, the worst case cost remains
quadratic. We introduce two means of improving the computational performance of
these methods, both based on parallelising the dynamic programming approach. We
establish that parallelisation can give substantial computational improvements:
in some situations the computational cost decreases roughly quadratically in
the number of cores used. These parallel implementations are no longer
guaranteed to find the true minimum of the penalised cost; however, we show
that they retain the same asymptotic guarantees in terms of their accuracy in
estimating the number and location of the changes.
