Adam Pearce
The drawdown of a series is the largest decrease in value between two points. If you were to purchase and sell a stock, the start and end of its drawdown would be the worst time to do so.
Since order matters, calculating drawdown isn’t as simple as finding the maximum and minimum values of the series - if the minimum occurs before the maximum, such an approach will identify a period of appreciation. To avoid this case, we can iterate over each index i of the series, then compare the price at time i to the price at all subsequent indices j. maxDrawdown is equal to the largest difference between prices at i and j:
var n = prices.length
for (var i = 0; i < n; i++){
for (var j = i + 1; j < n; j++){
dif = prices[i] - prices[j];
maxDrawdown = maxDrawdown > dif ? maxDrawdown : dif;
}
}
While accurate, this algorithm require many value comparisons:
If the series has n prices, n*(n - 1)/2 comparisons are needed (the number of comparisons done during the ith pass through the inner loop is n - i - 1; the sum of all those comparisons is 1 + 2 + 3 + ... + n - 1). The number of comparisons increases faster than n - if there are 100 values, 4950 comparisons are needed, while 200 values requires 19900 comparisons. For series covering a long period of time or with a great deal of granularity, this algorithm might be too slow even for a fast computer.
Instead of comparing every value with every other value, we can exploit the sequential requirement and make only n - 1 comparisons:
var peak = 0;
var n = prices.length
for (var i = 1; i < n; i++){
dif = prices[peak] - prices[i];
peak = dif < 0 ? i : peak;
maxDrawdown = maxDrawdown > dif ? maxDrawdown : dif;
}
Iterating over each index i of the series in order, the maximum decline ending at point i will start at the highest point of the series so far. While passing over the series we keep track of two numbers - the peak of the series and the maxDrawdown in price between peak and i.
The speed difference between the two algorithms is proportional to the number of prices. Calculating drawdown with the second approach on a series with 100 values takes 99 comparisons instead of 4950, which is 50 (100/2) times faster. A series with 200 values requires 199 comparisons instead of 19900, which is 100 (200/2) times faster. In general, since the first approach requires n*(n - 1)/2 comparisons for a series with n values and the second n - 1 comparisons, the second approach will be n/2 times faster.