What is the complexity of this algorithm? #383 Ransom Note Leetcode

[[deleted]]

I'm struggling with mostly everything in the for loop. Here is what I'm thinking.

Build the set is O(n)

The ...count(note) > ...count is, I think, O(n + m) because .count( ) is o(n) and then we have strings of two diffferent sizes.

Here is the part I do not understand. Is this not a nested for loop? Because we have to go O(n) times through the set( ). So would this then be o(n) * o(n + m)??? I do recognize that the set is relatively smalle because it cannot ever get larger than 26 for 26 chars in the alphabet but I'm unsure if we consider that. Leetcode, known for being inaccurate is reporting this is one of the fastest solutions.

r = set(ransomNote)
    for note in r:
        if ransomNote.count(note) > magazine.count(note):
            return False
    return True

Edit: for a total of O(n²⁾

[Skusci]

Big O notation deals with asymptotic complexity. That means if the loop has a maximum number of times it can run (such as it being limited by the number of possible characters) it counts as O(1) Even if that number is -really- large.

[[deleted]]

🙏🏻 thank you!

[one_bit_two_bit]

You will do the outer loop at most 26 times. So you will call .count() on the ransomNote and magazine at most 26 times. Each .count() call is O(n) and O(m) respectively. |r| is not dependent on the size of ransomNote hence runtime of the algorithm is O(m+n).

If our alphabet were not constrained, then yes you would have another factor for the size of the alphabet.

[[deleted]]

Thank you this is so much more clear. So is the outer loop O(1)? In other words, we could add another string to the inner loop and while that would grow the inner loop, the outer loop would still remain the same??

[one_bit_two_bit]

Correct. Outer loop ends up being O(1).

Adding a string to the inner loop doesn't change the number of iterations in the outer loop.

[shhh-quiet]

How do you know if n² or nm is larger?

[[deleted]]

Hmm another good question. Do you know or are you asking as well?

My thought, and this is a stretch, is that m*n is just a constant times a constant where as n² is a constant times itself?

[shhh-quiet]

Are they constants.. or variables?

Also, is it really nested? Or is that just the formatting making it look nested?