CODEWITHSUNDEEP
javascripttime-complexity
myTest532 myTest532
myTest532 myTest532

Reputation: 2381

Time Complexity Hash Table

I implemented a simple algorithm in 2 ways. One using indexOf and other one using Hash Table.

The problem: Given an arbitrary ransom note string and another string containing letters from all the magazines, write a function that will return true if the ransom note can be constructed from the magazines ; otherwise, it will return false.

First one. Is it Time Complexity O(N^2) because I have N letters in the ransomNote and I can do N searches in the indexOf?

var canConstruct = function(ransomNote, magazine) {
    if(magazine.length < ransomNote.length) return false;
    
    const arr = magazine.split("");
    for(let i=0; i<ransomNote.length; i++) {
        if(arr.indexOf(ransomNote[i]) < 0)
            return false;
        const index = arr.indexOf(ransomNote[i]);
        arr.splice(index, 1);
    }
    
    return true;
};

Second one. What is the time complexity? Does the hash table makes it O(N)?

var canConstruct = function(ransomNote, magazine) {
    if(magazine.length < ransomNote.length) return false;
    
    const map = new Map();
    for(let i =0; i<magazine.length; i++) {
        if(map.has(magazine[i]))
            map.set(magazine[i], map.get(magazine[i])+1);
        else
            map.set(magazine[i], 1);
    }
    
    for(let i=0; i<ransomNote.length; i++) {
        if(!map.has(ransomNote[i]))
            return false;
        else {
            const x = map.get(ransomNote[i]) - 1;
            if(x > 0)
                map.set(ransomNote[i], x)
            else
                map.delete(ransomNote[i]);
        }
    }
    
    return true;
};

Thanks

Upvotes: 0

Views: 167

Answers (2)

vukojevicf
vukojevicf

Reputation: 827

FIRST solution

Well one thing you have to take in consideration, especially in the first solution is that split, slice and indexOf methods all have their own time complexity.

Let's say you have m letters in magazine. When you split it into array, you will already use O(m) time complexity there (and of course O(m) space complexity due to the fact you store it all in a new array, that has a size of m).

Now you enter a for loop that will run n times (where n is the number of letters in ransomNote). So right then and there you have O(m * n) time complexity. indexOf operation will also be called n times with the caveat that it runs O(m) every time it's called. You can see there how quickly you start adding up your time complexity.

I see it being like O(3 * m * n^2) which rounds up to O(m * n^n) time complexity. I would strongly suggest not calling indexOf multiple times, just call it once and store its result somewhere. You will either have an index or -1 meaning it wasn't found.

SECOND solution

Much better. Here you populate a hash map (so some extra memory used, but considering you also used a split in first, and stored it, it should roughly be the same).

And then you just simply go with one loop over a randomNote and find a letter in the hashMap. Finding a letter in map is O(1) Time so it's really useful for this type of algorithm.

I would argue the complexity would be O(n * m) in the end so much better than the first one.

Hope I made sense to you. IF you want we can dive a bit deeper in space analysis later in the comments if you respond

Upvotes: 1

Barmar
Barmar

Reputation: 781190

The version with indexOf() is O(N*M), where N is the length of the ransom note, and M is the length of the magazine. You perform up to N searches, and each search is linear through the magazine array that's N characters. Also, array.splice() is O(M) because it has to copy all the array elements after index to the lower index.

Hash table access and updates are generally considered to be O(1). The second version performs N hash table lookups and updates, so the overall complexity is O(N).

Upvotes: 1

Related Questions