Update: these slopes are both linear, or O(n), where n is the input data size.
However for the worst performing algorithm, MTIE, an O(n*log(n)) algorithm that uses a binary tree to store intermediate results is possible. This algorithm restricts the tau-values to 2**k (with k integer) times the data interval.
Danny Price has made a fantastic contribution to allantools by taking my previous pure python code (hacked together in January 2014, shown in red) and numpyifying it all (shown in blue)!
For large datasets the speedups are 100-fold or more in most cases!
The speedups are calculated only for datasets larger than 1e5, since python's time.time() doesn't seem suitable for measuring 1 ms or shorter running times.