Complexity analysis is a thriving academic discipline, but we have to know that its results are true only at the limits. This means the theoretically faster algorithm could scale better and outperform the slower one only for big enough inputs, as it might have a big constant overhead. So, to restate it more succinctly, we'd like to cite Bob Pike's third rule of programming:
Fancy algorithms are slow when n is small, and n is usually small.
-Bob Pike
As has already been said—measure first, optimize later. Don't use complicated algorithms when there isn't any need for them. Judge wisely about if and when they are really needed.