Hello everyone,
I am in need of help. I have a school problem and I have to analize the code by its time and space complexity. Could someone help me break the space and time complexity of this code?
Thank you
function sortbyFrequency(arr) {
var sortAble = [];
var results = [];
let myMap = new Map();
arr.forEach(function(value) {
if ( myMap.has(value) ){
myMap.set(value, myMap.get(value)+1);
}else{
myMap.set(value, 1);
}
});
// decreasing sort
let newMap = new Map([...myMap.entries()].sort((a, b) => b[1] - a[1]))
newMap.forEach(function(value, key){
for (let i=0;i<value;i++) {
results.push(key);
console.log(results);
}
});
return results;
}```
Well, we’re probably not going to do your homework for you if that is what you are asking
I’m assuming you have learned about big O? Why don’t you give us your current interpretation of what this runs in and then we’ll help you through it if you aren’t quite on the right track.
So time complexity:
I am thinking that this code has a time complexity of 0(n*n), since it has one for loop nested inside forEach. This is for the whole code.
So the first part:
This part only has one foreach loop which is O(n) and if/else is if I am not mistaken 0(1).
let newMap = new Map([...myMap.entries()].sort((a, b) => b[1] - a[1]))
newMap.forEach(function(value, key){
for (let i=0;i<value;i++) {
results.push(key);
console.log(results);
}
});
And the second part has one forEach loop and for loop nested inside so I guess that makes it O(n*n).
And for the space complexity I am not really sure. I think .map() is not a constant so it has O(n). I think space complexity is O(n).
Let’s take each ‘section’ of the function one at a time.
Is there a for loop nested inside this forEach? My eyes could be playing tricks on me but I’m not seeing it. If I am correct, then you are looking at a linear growth rate, not quadratic.
I just updated my previous comment. We did not understnad each other, since that comment for nested for loop inside forEach was meant for the second part of the code.
Gotcha. You’re right, I misunderstood what you were saying.
If you google the JS sort you’ll see that it is safe to assume it runs in O(n log n). So I agree with you, the second forEach with the inner for loop, which runs in O(n*n) [sorry, don’t know how to do superscript here so I can’t write it properly as n squared] dominates this function and makes it O(n*n).
As for space complexity, I will admit I’m not as sharp on that one, so take this with a grain of salt. A Map will create as many entries as needed, so it grows linearly: O(n). You’re adding to a results array which also grows linearly. So it seems to me that you are correct, the space complexity is O(n).
You seem to have a pretty good understanding of this. Was there a particular reason you posted this question?
Thank you for your opinion. So your thinking is the same as mine.
The main reason for posting this question is that I am not sure if my space complexity analysis is correct. As I am quite new to this, we only had few lesson about it at the Uni and I did read about it on the web but I am unsure.
I think space complexity gets a little overlooked nowadays because we all have so much RAM in our computers that we can get away with ignoring it for the most part. Back when I started you were literally trying to save every byte you could
Good luck and keep up the good work. It appears to me that you are on the right track. And I apologize if I came off sounding like a jerk initially. Most of us here are happy to help people. And I like the out of the ordinary stuff like this. But we will always want to see what you’ve done first.
Yes I think it is not that important anymore, since the proccesors advanced so much. Specially for small programs it is not important anymore.
Oh, thank you and thank you for the help. Oh now it was my mistake that I havent’t posted my solution or thinking of it. I understand that some people just try to get it done the easy way and they just ask for solution.
So thank you again.
