Answer to: How to choose between brute force and efficient solution that has overhead?

When you have two algorithms, one which is simple to implement, but probably slow, and one which is probably much quicker, but more complex, and it needs more effort to implement you always start with the first. Even when you know for sure only the second one will meet your performance requirements, you will still need to implement the first one for the purpose of comparing the results, for testing whether you got the complex implementation of the second one right. If you are lucky, after you implemented the first (simple) one and tried it out, it may turn out it is already quick enough and you may save the effort for implementing the second one. If you are not so lucky, you need to invest this effort. Maybe it turns out the simple algo is not only useful for comparison purposes, but faster for small inputs, so you may combine both approaches. And if you are really unlucky, the second algo will not meet your performance requirements as well, and you have to look for third approach. Anyway, given there is a certain complexity involved, you will only find this out by making experiments and measuring.