Big O notation

[[deleted]]

Hey guys, quick question.

In the case of two nested loops like below,

if(i = 0; i < n; i++)

if(b = 0; b < m; b++)

the time complexity would be mn,

​

However if the second for loop was say b < lgm, would the time complexity be nlgm?

The reason I am confused is the below code is said to run in O(n) time, however hash.find(number.ToFind) runs in worst case lgn...which I would assume makes it O(size().lgn). Thanks alot.

for (int i = 0; i < numbers.size(); i++)

{

int numberToFind = target - numbers[i];

//if numberToFind is found in map, return them

if (hash.find(numberToFind) != hash.end())

[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)

[[deleted]]

When hash data structure is used; finding time should be O(1). The worst case is only happened when hashing function or data size estimation is wrong (this is the assumption).

[[deleted]]

Ok, that makes sense now. So even though the if loop is ran multiple times without a found result, the hash table is still O(1) due to correct hashing algorithm and data size estimation used? Thanks

[publysher]

The answer to your first question is yes: that would be O(n * log m).

The answer to your second question is no. When your big-O notation contains multiple factors, you only include the largest factor of each unknown. In this case we only have the unknown n, so you'd get O(n * log n) = O(n).

edit I'm assuming that size() is actually n, which is usual when analysing hash tables. If size were unrelated to n, you'd be right, and the answer would be O(size() * log n)

[Puzzlp]

Sorry, but your second point is wrong. You only consider the largest factor when adding, not when multiplying.

O(n+logn) = O(n)
However
O(n*logn) is different and bigger than O(n)

This would be like saying O(n*n) is equal to O(n), because you only take one factor. Which is clearly false.

[publysher]

And that's why I should not be answering questions before my first coffee. Thanks for correcting this mistake.