Is there better way to improve my algorithm of finding drawdown in stock market?

Question

I am trying to calculate drawdowns of every stock. Definition of drawdown is

A drawdown is a peak-to-trough decline during a specific period for an investment, trading account, or fund.

To put it simple, drawdown is how much does stock crash from peak to trough. In addition to that, drawdown is recorded when peak's price has recovered later at some point.

To calculate drawdown, I break up into 2 points

1. find peak(which price is greater than 2 adjacent days' prices) and trough (which price is lower than 2 adjacent days' prices)

2. When the peak's price has recovered, that peak, trough becomes a drawdown

Here is an example of stock quotation:

        data class Quote(val price: Int, val date: String)
        ...
        //example of quote     
        Quote(price:1, date:"20080102"),
        Quote(price:2, date:"20080103"),
        Quote(price:3, date:"20080104"),
        Quote(price:1, date:"20080107"),
        Quote(price:2, date:"20080108"),
        Quote(price:3, date:"20080109"),
        Quote(price:2, date:"20080110"),
        Quote(price:4, date:"20080111"),
        Quote(price:5, date:"20080114"),
        Quote(price:6, date:"20080115"),
        Quote(price:7, date:"20080116"),
        Quote(price:8, date:"20080117"),
        Quote(price:9, date:"20080118"),
        Quote(price:7, date:"20080122"),
        Quote(price:6, date:"20080123"),
        Quote(price:8, date:"20080124"),
        Quote(price:11,date:"20080125"),
        
        list of drawdowns by date: 
            (peak: "20080104", trough:"20080107", daysTakenToRecover: 3),
            (peak: "20080109", trough:"20080110", daysTakenToRecover: 2),
            (peak: "20080118", trough:"20080123", daysTakenToRecover: 4),

Here is what is wrote for a test case:

 class Drawdown {
              var peak: Quote? = null
              var trough: Quote? = null
              var recovered: Quote? = null
              var percentage: Double? = null
              var daysToRecover: String? = null
       }

       data class Quote(
            val price: Double,
            val date: String
       )
      
 class Test {
          private fun findDrawdowns(): List<Drawdown> {
          val list = mutableListOf<Drawdown>()
          var peak: Quote? = null
          var trough: Quote? = null
          var recovered: Quote? = null

    for (quotation in quotations) {
        val currentIdx = quotations.indexOf(quotation)
        if (currentIdx in 1 until quotations.size - 1) {
            val prevClosing = quotations[currentIdx - 1].price
            val nextClosing = quotations[currentIdx + 1].price
            val closing = quotation.price

            recovered = when {
                peak == null -> null
                closing >= peak.price -> {
                    if (peak.date != quotation.date) {
                        //can possibly be new peak
                        Quote(closing, quotation.date)
                    } else null
                }
                else -> null
            }

            peak = if (closing > prevClosing && closing > nextClosing) {
                if ((peak == null || peak.price < closing) && recovered == null) {
                    Quote(closing, quotation.date)
                } else peak
            } else peak

            trough = if (closing < prevClosing && closing < nextClosing) {
                if (trough == null || trough.price > closing) {
                    Quote(closing, quotation.date)
                } else trough
            } else trough


            if (recovered != null) {
                val drawdown = Drawdown()
                val percentage = (peak!!.price - trough!!.price) / peak.price

                drawdown.peak = peak
                drawdown.trough = trough
                drawdown.recovered = recovered
                drawdown.percentage = percentage
                drawdown.daysToRecover =
                    ChronoUnit.DAYS.between(
                        LocalDate.of(
                            peak.date.substring(0, 4).toInt(),
                            peak.date.substring(4, 6).toInt(),
                            peak.date.substring(6, 8).toInt()
                        ),
                        LocalDate.of(
                            recovered.date.substring(0, 4).toInt(),
                            recovered.date.substring(4, 6).toInt(),
                            recovered.date.substring(6, 8).toInt()
                        ).plusDays(1)
                    ).toString()
                list += drawdown
                peak = if (closing > prevClosing && closing > nextClosing) {
                    Quote(recovered.price, recovered.date)
                } else {
                    null
                }
                trough = null
                recovered = null
            }
        }
    }
    val drawdown = Drawdown()
    val percentage = (peak!!.price - trough!!.price) / peak.price

    drawdown.peak = peak
    drawdown.trough = trough
    drawdown.recovered = recovered
    drawdown.percentage = percentage
    list += drawdown
    return list
    }

For those who want to read my code in github, here is a gist:

Find Drawdown in Kotlin, Click Me!!!

I ran some test cases and it shows no error.

So far, I believe this takes an O(n), but I want to make it more efficient.

How can I improve it? Any comments, thoughts are all welcomed!

Thank you and happy early new year.

Answer 1

There are two points

1. unfortunately the current complexity is the O(N^2)

for (quotation in quotations) {
        val currentIdx = quotations.indexOf(quotation)
        ....

You have a loop through all the quotations, in which for each quotation you find its index. Finding the index is O(N) - look at indexOf docs. So total complexity will be O(N^2)

But you can easy fix it to O(N). Just replace foreach loop + indexOf with forEachIndexed, for example:

        quotations.forEachIndexed { index, quote ->
            // TODO
        }

2. I think it's not possible to make it faster than O(N), because you need to check each quotation.