CODEWITHSUNDEEP
javascriptbig-o
bigShaq
bigShaq

Reputation: 79

What is the Big-O of this Anagram checker

This is a piece of code I wrote to check if two strings are anagrams. This is not homework, I am learning DS&A by myself.

It seems to me that the big-O should be O(N) because there are 2 separate for-loops, but the second for-loop worries me, specifically the Object.entries() call. Is the final time complexity O(N) or O(N^2) here?

function isAnagram(origStr, checkStr) {

    if (origStr.length !== checkStr.length) {
        return false;
    }

    const origFreqCounter = {};
    const checkFreqCounter = {};

    let countFreq = (str, counter) => {
        for (const c of str) {
            counter[c] = counter[c] + 1 || 1;
        }    
    };

    countFreq(origStr, origFreqCounter);
    countFreq(checkStr, checkFreqCounter);

    // Is this O(N) or O(N^2)?
    for (const [key, value] of Object.entries(origFreqCounter)) {
        if (checkFreqCounter[key] !== value) return false;
    }
    
    return true;
}

console.log(isAnagram('', '')) // true
console.log(isAnagram('aaz', 'zza')) // false
console.log(isAnagram('anagram', 'nagaram')) // true
console.log(isAnagram("rat","car")) // false)
console.log(isAnagram('awesome', 'awesom')) // false
console.log(isAnagram('amanaplanacanalpanama', 'acanalmanplanpamana')) // false
console.log(isAnagram('qwerty', 'qeywrt')) // true
console.log(isAnagram('texttwisttime', 'timetwisttext')) // true

Upvotes: 0

Views: 181

Answers (1)

CertainPerformance
CertainPerformance

Reputation: 370799

Yes, it's O(n).

This function iterates over the string's length, no nested loops:

let countFreq = (str, counter) => {
    for (const c of str) {
        counter[c] = counter[c] + 1 || 1;
    }    
};

That function is called twice, and not in a loop, so that's O(n).

Then the Object.entries iterates over the entries of the origFreqCounter object. The origFreqCounter object will not have more entries than the number of characters in the origStr string, so that's also O(n).

O(n) + O(n) + O(n) = O(n).

Or, to be pedantic - the algorithm depends on the size of both origStr and checkStr, which are not necessarily the same, so it'd be more proper to call it O(n + m).

Upvotes: 2

Related Questions