How to avoid O(N²)
Hi, algorithm aficionados! Recently, I’ve started learning algorithms and found some patterns of making them faster. I’ll share one of them with you.
First of all, should we avoid O(N²)?
Of course, it depends on the situation. Some famous algorithms take O(N²). Don’t get me wrong. I never mean that we should not use algorithms needing O(N²). However, there are some cases in which it is possible to make algorithms faster with more thoughts. In particular, if we write code straightforwardly in some cases, the algorithms can be O(N²) easily. We have to pursue faster ones. OK, Let’s go.
Understanding the time complexity of build in methods
This might be most important. Recent high-level languages have tons of build-in methods. We need to know the time complexity of them in order to slow algorithms. For example…
[1,2,3,4,5].indexOf(5) // what is the time complexity?
[1,2,3,4,5].shift() // How about this one?These are famous build-in methods in JavaScript. They need O(N). Thus,
for(let i = 0; i < array1.length; i++){
array2.shift();
};
// => This time complexity if O(N^2)If they are written in a for loop, the time complexity become O(N²). At first glance, the algorithms don’t look so heavy, but we have to pay attention to it.
Using Two pointers
It might be possible to avoid O(N²) by using two pointers in a for loop. For example, assume that you are required to develop an algorithm which can find a pair that adds up to the target sum. If the codes are written straightforwardly, it will be like below.
function findPairForSum(array, target) {
for (let i = 0; i < array.length; i++) {
for (let j = i + 1; j < array.length; j++) {
if (array[i] + array[j] === target) {
return [i, j]; // Pair found
}
}
}
return [-1, -1]; // Pair not found
}
// Example usage:
const result = findPairForSum([1, 2, 4, 7, 11, 15], 13);
console.log(result); // This will output the indices of the pair that adds up to the target sum, if found.For statements are nested, which means the time complexity is O(N²). How can we improve it?
function findPairForSum(array, target) {
let left = 0;
let right = array.length - 1;
while (left < right) {
const sum = array[left] + array[right];
if (sum === target) {
return [left, right]; // Found the pair
} else if (sum < target) {
left++; // Increase the sum
} else {
right--; // Decrease the sum
}
}
return [-1, -1]; // Pair not found
}
// Example usage:
const result = findPairForSum([1, 2, 4, 7, 11, 15], 13);
console.log(result); // This will output the indices of the pair that adds up to the target sum, if found.The loop is only one, so the time complexity is O(N)! Ta-da!
Disassembling nested for statements
Next example is a method judging if given strings are isomorphic or not.
Nested loop version is below.
var isIsomorphic = function(s, t) {
let map_s = new Map();
let map_t = new Map();
for(let i = 0, j = 0; i < s.length; i++, j++){
if(!map_s.has(s[i])){
map_s.set(s[i], i)
}
if(!map_t.has(t[j])){
map_t.set(t[j], j)
}
for(let i = 0, j = 0; i < s.length; i++, j++){
if(map_s.get(s[i]) != map_t.get(t[j])){
return false;
}
}
}
return true;
};
And disassembled version is below.
var isIsomorphic = function(s, t) {
let map_s = new Map();
let map_t = new Map();
for(let i = 0, j = 0; i < s.length; i++, j++){
if(!map_s.has(s[i])){
map_s.set(s[i], i)
}
if(!map_t.has(t[j])){
map_t.set(t[j], j)
}
}
for(let i = 0, j = 0; i < s.length; i++, j++){
if(map_s.get(s[i]) != map_t.get(t[j])){
return false;
}
}
return true;
};That’s all? Yes, that’s all. Besides, it has a great impact on your algorithm. As a proof, if I submitted these algorithms to leet code, the result was like below.
The first one is the nested loop version and the second one is the disassembled version. There is a big difference.
Refer to my leet code =>
Using hash map
This is an effective approach as well. It could decrease the time complexity significantly! Assume the same problem (the findPairWithSum algorithm).
function findPairWithSum(nums, target) {
let numMap = new Map();
for (let i = 0; i < nums.length; i++) {
let complement = target - nums[i];
if (numMap.has(complement)) {
return [numMap.get(complement), i];
}
numMap.set(nums[i], i);
}
return [-1, -1];
}This is a hash map version. Hash map can be calculated with O(1). That’s why the time complexity is only O(N)!
Wrap up
As I write above, some famous algorithms such as bubble sort requires O(N²). So, N² isn’t absolutely evil. However, I would like you to take these techniques into consideration and use them for making your code faster!
