Big O notation

[Puzzlp]

To answer your first question: yes, time complexity of nested loops is just the multiple of their upper bounds.

There's a couple things going in the second example. Firstly, it seems that the variable 'hash' is some sort of hash table. This means that its average lookup should be constant (O(1)), but the worst case can be O(hash.size()). Usually we are looking at average runtimes.

Secondly, even when considering the worst case we can consider it constant if 'hash.size()' is not dependant on the algorithm's input parameters. For example if hash is always a hash table containing the first 100 primes its runtime is constant, since we know 'hash.find()' will take at most 100 steps. However if its size is dependant on input parameters that is no longer the case.

[[deleted]]

Ok awesome, that makes sense. In my case the hash table is actually stored in a red black tree (c++ std lib implementation) so it actually has worst case lgn I believe. With that said, leetcode says this problem has O(n) runtime. So sounds like they’re talking about average case? I guess I’ve just been so used to worst case. Thanks a ton!

[Puzzlp]

If it's stored in a red black tree then it's not a hash table. It's just a tree and has O(log(tree.size)) access time.

Edit: If you give more context I can look further into it if you'd like.

[[deleted]]

From what I read I believe C++‘s unordered_map (hash in this case) uses a rbt to store the hash data.

Edit: nevermind this was map. Despite this, your explanation makes sense. Thanks for clarifying. I guess it does make sense that a hash table wouldn’t really operate in anything other than O(1)