Discussion on: Time complexity Big 0 for Javascript Array methods and examples.

[Victor Cheeney]

People these days often use .reduce with spread .... So it becomes O(n^2). There're lots of articles (even on dev.to) which showcase such an approach. My experience of interviewing says me that people don't understand that there's a problem.

I'm not sure I understand what you mean, do have an example that would illustrate this kind of situation? Thanks!

[Mike]

I think he means something like:

const users = [
  {name: 'foo',  admin: false, dateRegistered: '2022-02-01', },
  {name: 'bar',  admin: false, dateRegistered: '2010-05-30', },
  {name: 'baz',  admin: true,  dateRegistered: '2009-12-25', },
  {name: 'spaz', admin: true,  dateRegistered: '2020-06-30', },
];

const admins = users.reduce((agg, user) => (
  !user.admin ? agg : {
    ...agg,
    [user.name] : user.dateRegistered
  }
), {});

Where ...agg is potentially being spread for each iteration over users. Instead of an internal traversal, use any kind of loop for O(n) time instead of O(n^2).

const users = [
  {name: 'foo',  admin: false, registered: '2022-02-01', },
  {name: 'bar',  admin: false, registered: '2010-05-30', },
  {name: 'baz',  admin: true,  registered: '2009-12-25', },
  {name: 'spaz', admin: true,  registered: '2020-06-30', },
]

const admins = {}
users.forEach((user)=>{
  if (user.admin) { admins[user.name]=user.registered }
})

reduce could be used, but was abandoned because it's absolutely unnecessary. for .. of (or any loop structure) could be used instead of .forEach. The latter was used as a manner of preference.

Note: it's actually something closer to O(n(n+1)/2) + O(n) where once coefficients and smaller figures are removed simplifies as O(n^2).