What do programmers mean when they use the term "BruteForce approach to the problem "?

Question

I wanted to understand what do programmers generally mean when they use the term " Brute Force " in their work .

Answer 1

Brute force is the application of a naïve algorithm to a problem, relying on computational resources instead of algorithmic efficiency to make the problem tractable.

@Guy Coder is correct that it often comes up when searching a data set, but it can be applied to other types of problems as well.

For example, supposed you needed to reverse the order of a linked list. Consider these approaches:

1. Adjust the pointers between the elements so that they are linked in the reverse order. That can be done in linear time with a fixed amount of memory.

2. Create a new list by walking the original list and pre-pending a copy of each element, then throw away the old list. That can also be done in linear time (though the constant will be higher) but it also uses memory in proportion to the length of the list.

3. Systematically create all possible linked lists until you discover one that's the reverse of the original list. It's an exhaustive search over an unbounded solution space (which is different than an exhaustive search of a finite data set). Since there are an infinite number of linked lists to try, no matter how much computing resource you can apply, it might never finish.

4. Like 3, but revised to generate and test all possible linked lists of the same length as the original list. This bounds the solution space to O(n!), which can be huge but is finite.

5. Start coding without an understanding of how to solve the problem, and iterate away until something works.

"Brute force" is technical slang rather than jargon with a precise definition. For different people, it will carry different connotations. Which of these solutions you consider to be "brute force" depends on what the term connotes for you.

For me, and many of the programmers and software engineers I've worked with, "brute force" carries these connotations:

• The application of brute force is an intentional engineering decision. Brute force might be selected because:

  • The brute force method is easy to get correct
  • To create a reference implementation to check the results of a more efficient algorithm
  • The more efficient algorithm is not known
  • The more efficient algorithm is hard to implement correctly
  • The size of the problem is small enough that there is not much difference between brute force and the clever algorithm

• A brute force solution must solve the problem. An implementation that attempts an exhaustive search of an unbounded space is not a general solution to the problem.

• "Brute force" is usually a superlative. We say, "I used the brute force solution" rather than "a brute force solution." The implication is that, for a given problem, there's one straight-forward, direct, and obvious algorithm most programmers would recognize (or come up with) as the brute force solution for a given problem.

For those like me who feel the term has all of these connotations, only approach #2 is brute force. Those who disagree aren't wrong. For them, the term carries different connotations.