What is the time complexity of Pattern matching in scala?

Pattern matching in most cases will be O(1) because you are usually matching against a small number or possible cases and each match is comprised of a few constant time operations on average.

Since pattern matching is achieved by calling unapply method on the matched object docs and optionally comparing extracted values, the time complexity will depend on unapplys method's implementation and can be of any complexity. There is no compiler optimization possible for general case because some pattern matches depend on data being passed to them.

Compare these scenarios:

List(1, 2, 3) match { case _ :+ last => ... // O(n) with respect to list length case head :: tail => ... // O(1) w.r.t. list length case _ => ... // O(1) - default case, no operation needs to be done } 

Most of the time we would pattern match something like a list to get head and tail split with :: - O(1) because unapply is simply returning head if it exists.

We usually don't use :+ because it's not common and expensive (library code):

/** An extractor used to init/last deconstruct sequences. */ object :+ { /** Splits a sequence into init :+ last. * @return Some((init, last)) if sequence is non-empty. None otherwise. */ def unapply[T,Coll <: SeqLike[T, Coll]]( t: Coll with SeqLike[T, Coll]): Option[(Coll, T)] = if(t.isEmpty) None else Some(t.init -> t.last) } 

To get last element of a sequence (t.last) we need to loop, which is O(n).

So it will really depend how you pattern match, but usually you pattern match case classes, tuples, options, collections to get first element and not last, etc. In such overwhelming majority of cases you'll be getting O(1) time complexity and a ton of type safety.

Additionally:

In the worst case here there will be m patterns each doing on average c operations to perform a match (this assumes unapply has constant time, but there are exceptions). Additionally there will be an object with n properties which we need to match against these patterns which gives us a total of: m * c * n operations. However, since m is really small (patterns never grow dynamically and usually written by a human) we can safely call it a constant b giving us: T(n) = b * c * n. In terms of big-O: T(n) = O(n). So we established theoretical bound of O(n) that is for cases where we need to check all n properties of an object. As I was pointing out above in most of the cases we don't need to check all properties/elements like when we use head :: tail where n is replaced with constant and we get O(1). It's only if we always do something like head :+ tail we would get O(n). Amortized cost I believe is still O(1) for all cases in your program.