Hello!
Back Again!
Yes. It has been a long time since you heard from me, I’ve been busy. For those not aware, I’ve been building akaani (https://useakaani.com) with whatever free time I had. Feel free to join our waitlist if you are interested in all the cool things we’ll be building to bring you the best of African food wherever you are.
I’ve been meaning to write about this ever since I had a conversation with someone on Twitter. I did find it difficult to explain this to him at the time, hopefully I can do better today.
MxN
What is MxN runtime? How do you know an MxN runtime? How does MxN compare with other runtimes? Let’s try to answer these questions.
Given a function with an array input func(numsArray){}
we say our runtime is O(n) if we visit each element of the array numsArray
only once. In a lot of cases, this is a good enough solution but that’s not the focus of this letter. Can we end up with an MxN in this case? NO. Because we only have one input variable numsArray
- which we treat is n.
Let’s take a look at another function, func2, that takes in a 2D array such that the function is now written as func2 (numsArray=[[],[],[]]){}
Here we see that a simple loop to list all the elements of numsArray will look something like this:
func2 (numsArray){
for(const i = 0; i<numsArray.length; i++){
for (cont j = 0; j<numsArray[0].length; j++){
console.log(numsArray[i][j])
}
}
}
Given the nested loop shown above, it is tempting to think it is O(n^2), however that is not the case. Yes, in the rare off chance the the array is a perfect grid 4*4 or 6*6 the mathematical computation will be exactly the same as an O(n^2) because M and N are the same (4,4). But this is not always the case, our input array could have been a 10*2 or 30*15 or some other random combination of numbers forming a 2D grid. Given that this is often the case with grids, the runtime is thus MxN since the grid is most likely not going to be a perfect one.
2D arrays are not the only input types that yield an MxN runtime either. Similar to 2D input array function, a function taking in two different 1D arrays can easily end up with an MxN runtime.
func3 (arr1, arr2){
for(const i = 0; i<arr1; i++){
for (cont j = 0; j<arr2; j++){
console.log(arr1[i] * arr2[j])
}
}
}
A function with two input strings will have a similar runtime if we visit each character of both strings in a similar manner.
Can we do better than MxN? Wait for it…it depends. It depends on your problem statement, however, it is unlikely. In most cases, an MxN solution is as good an O(n) solution.
O(n^2)
Detecting the difference between O(n^2) and O(MxN) can be done in two ways. The first and perhaps straightforward approach is, do I have a grid (2D array) input or two input variables of different sizes? If the answer is yes, then the chances that it is an MxN are higher than that of it being O(n^2).
If however, the input array is 1D or a single input, then the odds are higher that it is an O(n^2) solution. Here is how a typical O(n^2) piece of code will look like:
func4 (arr1){
for(const i = 0; i<arr1; i++){
for (cont j = 0; j<arr1; j++){
console.log(arr1[i] * arr1[j])
}
}
}
Here we see that this code will grow as the input size grows. If our array has 10 elements, we will have a total of 100 iterations. If we had a 100 elements, we’d have 10,000 iterations (mind blown yet?) We can see the exponential growth that follows our input size.
By comparison, func3 with an input of two arrays of length 4 and 10 respectively will give 400 iterations.
Conclusion
I hope this helps clear the difference between O(MxN) and O(n^2). While in a few instances an O(MxN) can end up looking like (On^2) due to M and N being the same value, it is not to be mistaken to have the same efficiency. In most of its applications, O(MxN) is an efficient solution similar to O(n).
Well, that is it for this week. As it was with this newsletter, if you feel like there’s something I should talk about next time, feel free to tweet at me or send me a message on Twitter.
Until next time.