Complexity of chaining methods in javascript

Question

I have a problem to determine the complexity of my algorithm because it use features of ES6 and of course they are chained methods. I already know some of basic complexity of those method for example the complexity of Array.prototype.map is O(n). But when we want to determine a complexity of an algorithm, how do we manage chained method ?

For example, consider we have a function which return for an array the sum of its positive numbers

let sumPositive = arr => arr.filter(i => i > 0).reduce((a, b) => a + b, 0);

console.log(sumPositive([1, 2, 3, -4])); // 6
console.log(sumPositive([1, 2, 3, 4])); // 10

Therefore, what is the complexity of that function ?

Another example is this algorithm which for a given string, return the counts of each character in the string

let charCount = str =>  str.split('').map(
  (c,_,str) => str.filter(i => i===c)
  ).reduce((a, b) => a.hasOwnProperty(b[0]) ? a : ({...a, [b[0]]: b.length}), {});

console.log(charCount("hi")); // {"h": 1, "i": 1}

console.log(charCount("hello to you")); // {"h": 1, "e": 1, "l": 2, "o": 3, " ": 2, "t": 1, "y": 1, "u": 1}

So for this second I need to know especially its complexity because we are dealing with nested method like the filter which is being call inside a map

So any general method to determine the complexity of such algorithm are welcome.

Note: All the complexity in this question is the time-complexity not space

Thanks

As far as I know O(n) * n is still O(n). Chaining can go too far still and if performance is the issue you can often accomplish everything faster with one reduce. — Dexygen
– Dexygen, Commented Jan 18, 2020 at 12:25
As an aside, you could use Generators to provide lazy execution to prevent multiple iterations if iterating over the same array multiple times causes performance issues. Your second example that counts characters is O(n^2), as for each character in the array we must search every other character in the array in the worst case. — Dan
– Dan, Commented Jan 18, 2020 at 13:14
So could you give me an example of what I can do to improve the code or some useful links ? @DanPantry — Patrissol Kenfack
– Patrissol Kenfack, Commented Jan 18, 2020 at 13:17
@Dexygen I think you meant O(n) + n. Because shouldn't O(n) * n will be n^2 like 2 * 2 will be 4. — Debu Shinobi
– Debu Shinobi, Commented Jul 26, 2021 at 20:16

Ajay Dabas · Accepted Answer · 2020-01-18 12:49:34Z

7

Chaining methods is actually just for convenience. map() or filter() returns an array. Now you can first put a name on the array, like let result = arr.map(...) and then do other stuff on that result array, or you can directly do something on the array returned by map() (or filter()), like map().filter().<more chaining if you want>.

So, it's equivalent to a sequential execution. Consider this example,

let sumPositive = arr => arr.filter(i => i > 0)
                            .reduce((a, b) => a + b, 0);

let arr = [1, 2, 3, -4];

let filteredArray = arr.filter(i => i > 0); // O(n)
let reducedResult = filteredArray.reduce((a, b) => a + b, 0); // O(n)

console.log(sumPositive(arr)); // 6
console.log(reducedResult) // 6

Now you see filter() takes O(n) and then reduce() takes O(n), so you get O(n) + O(n) ==> O(n) as your final time complexity.

I hope you can similarly find complexity for the second example. If you need assistance, let me know in the comments.

answered Jan 18, 2020 at 12:49

Ajay Dabas

1,4441 gold badge8 silver badges15 bronze badges

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

2 Comments

Patrissol Kenfack Over a year ago

And what about the nested method like a filter into a map ?

Ajay Dabas Over a year ago

For each iteration inside map()(for all chars in string str of length n), you're performing filter() on n elements. So, filter() takes O(n) and it's done n times inside map(). That gives you n*O(n) ==> O(n^2). Just try to think for loops. map() is like a for loop over n elements and inside it, you have another for loop over n elements(due to filter()). Hence, complexity is O(n^2)

Dan · Accepted Answer · 2020-01-18 13:34:52Z

@Ajay Dabas answered your question; I'm answering your question in the comments:

So could you give me an example of what I can do to improve the code or some useful links

Your first example isn't going to get any simpler, but you could decrease the time complexity of your second algorithm:

let charCount = str =>  str.split('')
  .map((c,_,str) => str.filter(i => i===c))
  .reduce((a, b) => a.hasOwnProperty(b[0]) ? a : ({...a, [b[0]]: b.length}), {});

You could do this by not using the filter() method. There's no need to do this if you maintain an index of all of the keys and their current counts.. and you're already doing that with reduce():

    let charCount = str => 
        return str.split('').reduce(
            (acc, nextChar) => {
                return {
                    ...acc,
                    [nextChar]: (acc[nextChar] || 0) + 1
                };
            },
            Object.create(null)
        );
    };

This should be O(n) - We only iterate the array twice. Notice how we do not need to filter() the results because all we need to do is take the existing count for that character in the accumulator and increment it by one.

The usage of Object.create(null) is to create a new object with a null prototype - that means we don't need to use hasOwnProperty().

You should keep in mind that just because something is O(n^2) does not mean there is a performance problem. Big O notation just describes how some code will behave as the input data increases. Only look to optimize code when you know it's a problem.

Collectives™ on Stack Overflow

Complexity of chaining methods in javascript

2 Answers 2

2 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

2 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related