Look we can compare regular expressions by constructing their DFA
If L(M1)=L(M2)
Now for each N input Regular Expression there will be At most 2^n States in it's DFA(may be less, but this is the upper bound)
so simply the complexity will be O(2^n)
correct me,if needed :D