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!

Improve this question
2
  • What are you trying to archive? Because your filter method is not really filtering anything Commented Dec 30, 2021 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? Commented Dec 30, 2021 at 12:00

2 Answers 2

Reset to default
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.

Improve this answer
Sign up to request clarification or add additional context in comments.

5 Comments

The inner loop is not n it's m as it's the length of item.keys
Oh! sorry I missed that. thanks, @pilchard
Why O(n^2)? Doesn't the inner loop iterate over m keys in a single item and not over n items?
It should be O(m ^ 2 * n) where m is the number of keys.
Thank you for helping out its useful to know all this :)
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.

Improve this answer

6 Comments

You're missing the complexity of Object.keys()
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()?
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).
@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.
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).
|

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.