I am working on some leetcode tests and I am confused on the difference between a ‘linear search’ and ‘brute force’ algorithm, are they essentially the same thing?
For example, I have the below code that finds the subarray with the largest sum, and returns its sum.
I’m not sure if I have used a ‘linear search’ or ‘brute force’ algorithm in this instance?
const maxSubArray = function(nums) {
let max = 0
for (i = 0; i < nums.length; i++) {
let totalSum = 0
for (j = i; j < nums.length; j++) {
totalSum += nums[j]
max = Math.max(totalSum, max)
}
}
return max
};
maxSubArray([-2,1,-3,4,-1,2,1,-5,4]); // 6
2
Answers
‘Brute Force’ is typically used to refer to the application of an algorithm that’s significantly less efficient than an optimal algorithm for a given problem. While there are all kinds of in-between complexities, the major ones are:
So the confusion around whether linear search in a list is ‘brute force’ or not comes about because for sorted lists there’s a log-time solution (binary search), and for unsorted lists the best you can do is linear.
The term "brute force" is typically applied to algorithms that test every candidate solution in order to give an answer. That can lead to algorithms with varying complexities.
Linear search is a brute-force O(n) algorithm that tests every possible element in an array looking for a match. The Maximum Subarray Problem admits an O(n^2) brute-force algorithm (like yours, testing all subarrays) while a linear algorithm is known. A brute-force algorithm to the Traveling Salesman Problem runs in O(n!) time, testing all possible permutations of nodes.
In fact, for many NP-hard problems, we don’t know any algorithms with better complexity than a brute-force enumeration of the search space.