Nested loops and time complexity

Nested loops are loops within loops. They help when you need to compare each item in an array to all the other items, or to items in another array.

You are given two arrays with a set of numbers. Return an array of the numbers that are found in both arrays.

const set1 = [2, 5, 6, 87, 13, 90];
const set2 = [2, 6, 43, 67, 13, 90];

Solution 1: Brute-forced method with a nested loop

const results = [];

// loop through set1
for (let i = 0; i < set1.length; i++) {
	// loop through set2 for every item in set1
	for (let j = 0; j < set2.length; j++) {
		// if the number in set1 match the number in set2
		// at the same index, push that number to results
		if (set1[i] == set2[j]) {
			results.push(set1[i]);
		}
	}
}

return results; // [2, 6, 13]

This was what I usually did. It was easy for me to verbalize, especially early in my programming experience. It works but it’s not ideal.

For every item in set1, loop through every item in set2 and compare the items in the same index. The operation would happen 5 times for 5 items, therefore n x n. Since the length n was the same, it was n². In other words, this nested loop has a time complexity of O(n²). This means that as the size of the data set increases, the number of operations required to execute the operation would increase at a rate of n², relative to another algorithm achieving the same solution.

Solution 2: Using array methods

const results = set1.filter((item) => set2.indexOf(item) !== -1); // [2, 6, 13]

// or

const results = set1.filter((item) => set2.includes(item)); // [2, 6, 13]

For every item in set1, return it only if it also exists in set2.

This solution may not necessarily be faster since .filter(), .indexOf(), and .includes() still need to iterate through the items, but it’s much more elegant and easier to read.

.indexOf() looks for an item starting from some index (default is 0) and returns the index if found, otherwise it returns -1.

.includes() works the same as .indexOf(), but returns true if the item is found.

For small datasets, the difference between using a nested loop and an array method like .filter() is negligible.

How do these solutions compare to Objects?

Looking up a key/value pair in an object has a time complexity of O(1), meaning it is quick and constant.

If we take the same arrays above and convert them into objects whose keys are strings of their numerical values, we can compare the two objects by looping over one set, and doing a lookup of the other set.

const set1 = {
	two: 2,
	five: 5,
	six: 6,
	eightySeven: 87,
	thirteen: 13,
	ninety: 90,
};

const set2 = {
	two: 2,
	fortyThree: 43,
	six: 6,
	sixtySeven: 87,
	thirteen: 13,
	ninety: 90,
};

// iterate over Object
for (key in set1) {
	if (set1[key] === set2[key]) {
		console.log(key);
	}
}

Here, set1[key], set2[key], and === are O(1), but this method overall has a time complexity of O(n) - as the number of key/value pairs in a set increases, so will the number of times the comparison operation executes. Therefore, object lookup and search is much faster compared to arrays.