0

I'm fairly new to Big O and I am not sure what the time complexity of the following code will be:

const items = [
  {type: 'phone', name: 'iPhone', color: 'gold'},
  {type: 'phone', name: 'Samsung', color: 'gold'},
  {type: 'laptop', name: 'Chromebook', color: 'gray'},
  {type: 'tv', name: 'LG', color: 'gray'},
  {type: 'gooo', name: 'LG', color: 'silver'},
  {type: 'phone', name: 'Nokia', color: 'gold'}
];

items.filter(item => {
    for(let i=0; i < Object.keys(item).length; i++) {
        console.log('item is', Object.keys(item)[i])
    }
})

Can we say this is O(i + c) where i is items and c is the constant console.log? Or do we need to say something like O(i * j + c) where j is the individual item i.e. {type: 'phone', name: 'iPhone', color: 'gold'}

Can someone please help me out... thank you in advance!

Mohammed
  • 555
  • 1
  • 6
  • 19
  • What are you trying to archive? Because your filter method is not really filtering anything – Julius Dec 30 '21 at 11:55
  • It's actually a little more complicated because of the way you are calling `Object.keys()` which itself has a complexity of O(n) (you are calling it once per iteration in the `for` condition and again in the console.log) see: [Object.keys() complexity?](https://stackoverflow.com/a/64912755/13762301) – pilchard Dec 30 '21 at 12:00

2 Answers2

1

The items.filter(() => { ... }) is a loop => O(n).

You have a for loop inside of it looping over the object keys => O(m * n).

The Object.keys() is O(m) in V8 and you have it twice in the for loop (in the condition so it's called in every iteration and in the loop body) so it's => O(m ^ 2 * n) (where m is the number of keys).

Also, you can use

for (let key in item) {
  // and do whatever you want with the key
}

instead of using Object.keys.

Ahmed Mahmoud
  • 148
  • 1
  • 6
0

Let me change your code a bit:

items.filter(item => Object.keys(item).forEach(key => console.log("item is", key)));

The lambda is executed for every item in items. The lambda iterates over every key in an item and prints it. The time complexity is therefore O(n*m) for n = number of items and m = number of keys per item. If the number of keys per item is fixed and relatively small, you can assume O(n). The big O notation is just an rough estimate about the runtime, constant factors aren't that interesting.

Green绿色
  • 1,620
  • 1
  • 16
  • 43
  • You're missing the complexity of `Object.keys()` – pilchard Dec 30 '21 at 12:14
  • When we say "relatively small", what does that roughly look like? as in where do we draw the line to consider O(n) (or not)? And yes also... as @pilchard mentions, do we consider `Object.keys()`? – Mohammed Dec 30 '21 at 12:18
  • I guess, that's negligible. Calling `Object.keys` has a complexity of O(m) and it is called once for every item. The `forEach` loop has a complexity of O(m) as well and is also called once for every item. The filter condition hence has a complexity of O(2m) = O(m). – Green绿色 Dec 30 '21 at 12:19
  • @Mohammed It depends. In this example, I'd say, if the number of keys is constant (i.e., the items have a "schema"), but the number of items unbounded, then the number of keys is negligible. If, however, the number of keys is in practice unbounded (no fixed "schema"), then m should be considered as well. – Green绿色 Dec 30 '21 at 12:21
  • Note: The reason I changed the code is that calling `Object.keys` within the inner loop body is unnecessary. It just needs to be called once per item, which reduces the complexity a lot (cf. Mahmoud's answer). – Green绿色 Dec 30 '21 at 12:27
  • Yeah I think that makes sense. Thanks a lot I think I got my answer... it basically boils down to O(n*m) where n is items and m is no of keys per item :) (in your version of course) – Mohammed Dec 30 '21 at 12:33