I am trying to understand and state the Big O Notation of the following algorithm using reduce(). My understanding is that reduce is a function applied to an array object. It takes in a callback & an initialValue. The code below is a controller that holds the algorithm:
export const getPublicID = (req, res) => {
const data = req.body.result;
if (!data) res.status(422).json({ success: false, message: 'Upload Failed!' });
console.time('ARRAY');
const insertStuff = data.reduce((array, item) => {
array.push({
public_id: item.public_id,
url: item.url,
thumbnail_url: item.thumbnail_url
});
return array;
}, []);
console.timeEnd('ARRAY');
Photo.insertMany(insertStuff)
.then(
img => res.status(201).json({
success: true,
message: 'Successfully added to database.',
cloudinary: img
}),
err => res.status(422).json({ success: false, message: err })
);
};
The req.body.result comes in as an array of objects and through the reduce method I am creating my own array of objects that I then insert in my MongoDB collection.
Reduce is looping through the array so my thought is this is O(n), since the more elements present the more time it will take to iterate over, thus a linear graph. If that is the correct assumption my three questions are how do the following effect my algorithm:
push()insertMany()Thanks for helping a noob to data structures and algorithms out with understanding the pros and cons of the code, I greatly appreciate it!
The Big O describes asymptotic performance, and more specific it gives the upper bound for time complexity of an algorithm. This means that it doesn't look at how much actual time a function takes, could be 1 ms could be 1 min, just at how efficient your algorithm is.
O(n) means that the script will run in linear time. Example of that would be:
for(int i=0; i<n; ++i) {
print(i);
}
Now if you then need to run trough that array again, you'll get a different performance.
O(n^2) = O n squared = Outer loop (i) x outer loop (x)
for(int i=0; i<n; ++i) {
for(int x=0; x<n; ++x) {
print(x);
}
}
Now looking at what you're doing, you're on the right track with your analysis and you don't have a loop inside of a loop, just sequential loops.
There's the push(), although it's determined by reduce() rather than push(). There's the insertMany() which has the promise as a part of it. It's not an additional loop, just a function that's being executed.
This means that you have two loops. Some people would say that this gives you O(2n) but others claim there's no such thing, nor would it make a difference.
Bottom line: Looking at the purpose of Big O, it focuses on growth rate which is still linear, which still gives you O(n).