What is the runtime complexity of a switch statement?

Fragsworth picture Fragsworth · Dec 14, 2010 · Viewed 19.8k times · Source

I'd like to know what the worst-case runtime complexity of a switch statement is, assuming you have n cases.

I always assumed it was O(n). I don't know if compilers do anything clever, though. If the answer is implementation-specific, I'd like to know for the following languages:

  • Java
  • C/C++
  • C#
  • PHP
  • Javascript

Answer

lijie picture lijie · Dec 14, 2010

It is at worst O(n). Sometimes (and this is language and compiler dependent), it translates to a jump table lookup (for "nice" switches that don't have too large a case range). Then that is O(1).

If the compiler wants to be funky, I can think of ways that the complexity can be implemented to be anything in between (e.g. perform binary search on the cases, for logn). But in practice, you're going to get eiher linear time or constant time.