Big O for function chains in JS

Question

If I have something like

function aclean(arr) {
    let results = new Map();

    arr.forEach((word) => {
        const lc = word.toLowerCase().split('').sort().join('');

        if (!results.has(lc)) results.set(lc, word);
    });

    return Array.from(results.values());
}

Which takes an array of words, and filters anagrams by sorting a word alphabetically, storing it as a Map key and storing the unsorted word ( first one it finds ) as it's value, then carrys on. It then returns an array of the Map values.

So for ['bat, 'tab', 'bike'] it will return ['bat, 'bike'] as 'bat' is the first anagram of 'bat' it finds, so 'tab' is removed.

For this function am I correct in my assumptions:

arr.forEach is N - each word is visited once.

-- then inside loop
toLowerCase is ~C as each char is visited once and converted
split is C as
sort is ~ C Log(C) assuming quick sort
join is again C as each char is visited and added to a new array.

-- outside loop
results.has and .set are constant
Array.from(results.values()) is R as each value will be visited in the Map and pushed to a new array.

So overall I have a N * ( a lot of C + C .. + C Log (C) ... + C ) + R Which simplifies to N * C Log(C) + R - where C will be the largest string length?

And I'm assuming I can cancel off R as it's impact will be far less than the other two terms?

Big O for function chains in JS

0 Answers