1

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:

  1. push()
  2. insertMany()
  3. the promise

Thanks for helping a noob to data structures and algorithms out with understanding the pros and cons of the code, I greatly appreciate it!

rockchalkwushock
  • 1,143
  • 2
  • 9
  • 19

1 Answers1

3

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).

Robert
  • 1,899
  • 1
  • 17
  • 24
  • so for the most part, speaking hypothetically, if you are wanting to look at the Big O notation of an algorithm you can ignore promises which makes sense because a promise is just waiting for whatever variable we've declared the promise to be. I was unsure about `push()` so it is considered a loop? – rockchalkwushock Jan 05 '17 at 17:59
  • 1
    @cody, it's about the logical efficiency. So if you have a set of 10 items and for each of those items (loop) you run 1 function or 3 functions, it does not matter in the eyes of asymptotic performance. It's still linear because it does not change based on the input. If on the other hand you have 10 items and each of those contains 10 more items that you need to do something with, you then have a loop inside a loop. 'push()' is not the loop, but the function that's run by the loop 'reduce()'. This method runs a function on each element, therefore you can see that as a loop. Hope this helps. – Robert Jan 06 '17 at 09:31
  • @Robert -- so could we say that doing something like.... `myArray.reduce().reduce()` would also be equivalent to O(2n) or O(n) ? – cjones26 Feb 25 '20 at 03:30