3

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
}
pathikrit
  • 32,469
  • 37
  • 142
  • 221
  • Pretty sure the complexity depends on the implementation. As to @tailrec, it is used to enforce tail recursion (i.e. Throw a compiler error when something is annotated but not tail recursive) tail recursive functions are optimized automatically. Scala does not have full Tail Call Optimization though. – Angelo Genovese Jul 08 '15 at 21:16
  • According to http://www.scala-lang.org/api/2.11.5/index.html#scala.collection.immutable.List scala List "has O(1) prepend and head/tail access" regarding time performance while the space cost of tail is none and I think likewise for head although it is not stated. There is a table of collection time performance characteristics at http://docs.scala-lang.org/overviews/collections/performance-characteristics.html that shows time performance of ArraySeq is same as List for head but Linear in seq length for tail. –  Jul 08 '15 at 21:24
  • Is there anyway I can keep the same code and have it be O(n) time and O(1) space? – pathikrit Jul 08 '15 at 23:53

1 Answers1

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
}
bjfletcher
  • 11,168
  • 4
  • 52
  • 67
  • 2
    @bjfletcher "O(2n)" isn't really a thing. – Travis Brown Jul 08 '15 at 21:41
  • @TravisBrown I find it quite surprising that it does two loops over the sequence and I thought it was worth noting. How'd you write it? "O(n) - it does two loops in fact"? Thanks :) – bjfletcher Jul 08 '15 at 21:44
  • How can I keep the same nice recursive code and do it in O(n) time? I know I can ofcourse use IndexedSeqs to quickly look at start and end and keep pointers around but that feels dirtier.. Why isn't there a O(1) time tail extractor? – pathikrit Jul 08 '15 at 23:55
  • @bjfletcher I'd just say something like "and it traverses the sequence twice". As abuses of notation go, "O(2n)" isn't that terrible, I guess, but you're opening yourself to quibbling (from people like me, sorry :)). – Travis Brown Jul 08 '15 at 23:58
  • Would you like me to update answer with new extractor ideas? Let me know and I'll do it tomorrow. @Travis, don't be sorry - I enjoy learning how to improve this technical penmanship. :) – bjfletcher Jul 09 '15 at 00:59
  • New extractor ideas sounds good! No reason that extractor for tail should be O(n) for sequences that have O(1) tail ? – pathikrit Jul 09 '15 at 17:33
  • @wrick `middle` for `IndexedSeq` is `O(n)`. I've used `Vector` here for `O(1)` pattern matching. See updated answer. :) – bjfletcher Jul 09 '15 at 18:28