So, unfortunately my math isnt the greatest. That said, i dont understand how the solution became O(n). I understand the hashtable idea, but where did we figure out that it was O(n) instead of the other two? Is it because wikipedia gave us that formula and we just had to match what algorithm we used? If so, how do i know the name of the algorithm when i understand the code side of things but dont know the formal term?
Thanks in advance.
It’s O(n) because we know that each operation in a hash table is O(1) in the size of the input. We use it O(n) times so the result is O(1 x n) = O(n)
Thanks for the response.
So, each operation that uses a hashtable is O(1), so if i do two loops on a hashtable thats O(2)? Where do you find that a hashtable is O(1). For example if i use an array and do two loops on that what would the Big-O be and where would i find its formula?
Thanks again, i think its making a little more sense now, assuming my question makes sense 