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

what time , space complexity this:

def ispalindrome[a](x: seq[a]): boolean = x match {   case h +: middle :+ t => h == t && ispalindrome(middle)   case _ => true } 

does depend on implementation of seq? since indexedseq should have o(1) tail vs o(n) linearseqs? space complexity o(n) because of recursive call stack or scala 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 } 

does depend on implementation of seq? since indexedseq should have o(1) tail vs o(n) linearseqs?

i assume extractor o(n). extractor seq scala.collection.:+ has o(n) list last , o(n) last. code 2 following:

  def init: repr = {     if (isempty) throw new unsupportedoperationexception("empty.init")     var lst = head     var follow = false     val b = newbuilder     b.sizehint(this, -1)     (x <- this) { // o(n)       if (follow) b += lst       else follow = true       lst = x     }     b.result   }    def last: = {     var lst = head     (x <- this) // o(n)       lst = x     lst   } 

is space complexity o(n) because of recursive call stack or scala tail call optimization automatically?

i see code have optimization. makes sense because t && ispalindrome(middle) allows scala close current call stack, pass t on next stack &&ed with, , hence being tail-recursion optimisation-able.

constant time matching

using vector 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) => == l && ispalindrome(middle)   case _ => true }