Programming is really interesting, you can solve many problems through programming. But how to make your code more efficient and solve problems faster is also a problem faced by many programmers. And this has to be mentioned in Big O asymptomatic analysis. Next, I will use some questions to help you understand the concept of big O.
Here is the question: given 2 arrays, array1 and array2. We need to check whether there are duplicate items between the two arrays. If there are duplicate items, return true; otherwise, return false.
let array1 = [“a”, “b”, “c”, “d”, “e”];
let array2 = [“x”, “y”, “z”, “e”];
Example: array1 and array2 have a common character “e”, return true.
Before you continue to scroll down, try to solve this problem on your own.
Take a look at this solution, you may use forEach or for loop to loop through every item in both arrays and compare them. This is definitely correct! Congratulations! But let us analyze the operation of this code.
The first for the loop needs to take 5 operations to loop through the array1, and the second nested for loop will take 4 operations to loop through the second array. Let’s do the math, 5 times 4 equals 20 operations. And the time took to complete the task is less than 0.001 ms.
In Big O this is O(a*b) or O (n²);
You might think that 20 operations are nothing to modern computers. But what if these arrays scaled up to 100 or 1000 items or even more.
Let’s modify the arrays and replace with following code.
let array1 = new Array(10000).fill(“a”);
let array2 = new Array(10000).fill(“b”);
array1.push(“b”);
array2.push(“c”);
Now, the exact same code requires about 100,000,000 = 100 million operations to complete the task and takes about 700ms.
Take a look at the picture below, our code is O(N^2), which falls in the red zone.
And we need to make our code more efficient, but how can we do it?
Now. let’s take a look at this solution, we create an object called a map, and store every element as a property of the map object. and then create another for loop to loop through the second array and do the comparison at the same time.
In theory, as long as the number of operations is reduced, the running time will also be reduced accordingly. Now let’s check the result.
The results are very pleasant. We have successfully reduced the running time by nearly 200 times, and maintain the accurate result.
Gameshark / Secret trick：😎
O(N^2) = N x N = 10,000 * 10,000 = 100,000,000
O(N) = N = 10,000
100,000,000 > 10,000
