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