Are all brute force algorithms exponential?

Question

Every example I have seen of brute force algorithm has exponential run time.

Is this a strict rule, i.e. are all brute force algorithms exponential in run time?

Answer 1

No, certainly not. Consider a linear search algorithm to search a sorted array. You can do better, but a linear search could be considered "brute force".

See https://en.wikipedia.org/wiki/Brute-force_search for further examples and explanation. A relevant quote from that page:

While a brute-force search is simple to implement, and will always find a solution if it exists, its cost is proportional to the number of candidate solutions - which in many practical problems tends to grow very quickly as the size of the problem increases.

Answer 2

Nope. You can also do worse.

Example, finding the shortest tour (travelling salesman) using brute force is Omega(n!), which is not exponential.