What is the time and space complexity of a Scala's head/tail extractor?

Question

What is the time and space complexity for this:

def isPalindrome[A](x: Seq[A]): Boolean = x match {
  case h +: middle :+ t => h == t && isPalindrome(middle)
  case _ => true
}

Does it depend on the implementation of Seq? Since IndexedSeq should have O(1) tail vs O(n) for LinearSeqs? Is the space complexity is O(n) because of the recursive call stack or does Scala does tail call optimization automatically?

import scala.annotation.tailrec

@tailrec def isPalindrome[A](x: Seq[A]): Boolean = x match {
  case h +: middle :+ t => h == t && isPalindrome(middle)
  case _ => true
}

Answer 1

Does it depend on the implementation of Seq? Since IndexedSeq should have O(1) tail vs O(n) for LinearSeqs?

I would normally assume so however the extractor is actually O(n). The extractor for any Seq is scala.collection.:+ which has O(n) for the list up to the last and O(n) for the last. The code for those two are the following:

  def init: Repr = {
    if (isEmpty) throw new UnsupportedOperationException("empty.init")
    var lst = head
    var follow = false
    val b = newBuilder
    b.sizeHint(this, -1)
    for (x <- this) { // O(n)
      if (follow) b += lst
      else follow = true
      lst = x
    }
    b.result
  }

  def last: A = {
    var lst = head
    for (x <- this) // O(n)
      lst = x
    lst
  }

Is the space complexity is O(n) because of the recursive call stack or does Scala does tail call optimization automatically?

I see that the code does have this optimization. It makes sense because t && isPalindrome(middle) allows Scala to close the current call stack, pass t over to the next stack to be &&ed with, and hence it being tail-recursion optimisation-able.

Constant time matching

Using Vector we can achieve O(1) time:

object ends {
  def unapply[T](t: Vector[T]): Option[(T, Vector[T], T)] =
    if (t.length < 2) None
    else Some((t.head, t.drop(1).dropRight(1), t.last))
}

def isPalindrome[A](x: Vector[A]): Boolean = x match {
  case ends(i, middle, l) => i == l && isPalindrome(middle)
  case _ => true
}