Hi Manikanda,
GHC does compilation by transformation and hence goes through a series of intermediate languages (like Core and STG) which are better suited for optimizations. Pattern matches are transformed into a sequence of case expressions.
To answer you question, O(1) for simple patterns, but it really depends on the complexity of the pattern-matching expression and the Core-to-Core transformations that GHC applies. To truly understand the complexity, you need take a look at the Core/STG dump (I prefer STG since it's simple). If you have any particular code samples you'd like me to help you analyze, I'd be happy to do so.
A basic example:
---
data Color = Red | Blue | Green
isRed Red = True
isRed _ = False
---
GHC will transform this to
---
isRed x = case x of { Red -> True; DEFAULT -> False }
---
You can think of a case as a switch expression in your standard imperative languages. A case expression will evaluate the thunk 'x' and perform a switch on the tag of the result. Each data constructor has an integer tag associated with it which will be the target of the switch. So the time complexity of `isRed` will be the time complexity of thunk evaluation which is impossible to predict because a thunk can be incredibly complex. Lazy evaluation is not so easy to analyze. It is highly context-sensitive.
Hope that helps!
Rahul Muttineni