Array and List recursion performance

Question

I solving the problem of "Best-time-to-buy-and-sell-stock" at leetcode https://leetcode.com/problems/best-time-to-buy-and-sell-stock/description/ with 2 approaches:

1. With first, I transformed Array to List and handle list recursively:

    def maxProfit(prices: Array[Int]): Int = {
    @tailrec
    def maxProfitHelp(prices: List[Int], maxProfit: Int, lastBuy: Int): Int = {
      prices match {
        case Nil => maxProfit
        case head :: tail => if (head > lastBuy)  {
          maxProfitHelp(tail, Math.max(maxProfit, head - lastBuy), lastBuy)
        } else {
          maxProfitHelp(tail, maxProfit, head)
        }
      }
    }
   
    val listPrices = prices.toList
    maxProfitHelp(listPrices.tail, 0, listPrices.head)
   }
   

This gave time performance 962 ms. (Memory: 71,70 MB)

2. With second I tried to handle original array in the same recursive manned.

   def maxProfitWithoutList(prices: Array[Int]): Int = {
     @tailrec
     def maxProfitHelp(prices: Array[Int], maxProfit: Int, lastBuy: Int): Int = {
      prices match {
       case c if c.isEmpty => maxProfit
       case c => if (c.head > lastBuy)  {
        maxProfitHelp(c.tail, Math.max(maxProfit, c.head - lastBuy), lastBuy)
        } else {
           maxProfitHelp(c.tail, maxProfit, c.head)
        }
      }
    }
   
     maxProfitHelp(prices.tail, 0, prices.head)
   }
   

And time performance is 9134 ms. (Memory: 75,47 MB)

So with Array-recursion complexity is 10 times worse (!) as with List-recursion!

Why did this happen?

Answer 1

1. Previously when using leetcode I have quite often encountered even the same code having vastly different runtimes (though not 10x), so try submitting the same solution several times or better use appropriate tools for benchmarking

2. From what I can see Array.tail returns Array[T] which means that a new array should be constructed and have data copied to it (hence O(n)) unlike with List which is:

   immutable, linked-list class

   which means that tail operation should be extremely fast (O(1)).