I have been struggling for a few hours in terms of finding the right solution for the following problem:
Suppose we have a file that contains integers where each represents a user of a service. By reading that file we want to find how many times the service was accessed and by how many different users. My code should print something like "The service was accessed 500 times by 132 different users". Options to implement this might differ, use an ADT of your choice. Try to find a fast way to do this.
My initial thought after reading the material was to use the ADT Sorted Map and then use an AVL tree to store the different users based on their respective integer as key. I could change the value to how many times they accessed, but we don't need that, so I decided to skip the effort.
My thought was that for every integer in the file I'd check if the key exists in the AVL tree and then if it does just continue, if it doesn't add a node for it with the respective key.
At the end of it I'd request for the algorithm to print the number m (counter for each iteration) and use size() of the tree to get the amount of users.
If I did the calculations correctly then that would give me a complexity of $O(m \log^2n)$, where $m$ is the total amount of accesses and $n$ is the amount of users. In class we usually work with $O(\log n)$ or $O(n\log n)$ or $O(m\log n)$ and others, but I've never come across $O(m\log^2n)$ before, so I don't really understand if it's fast, if it's time consuming, and it's causing me doubt about my choice of method.
My questions for the community are:
- Can you give me an idea of how good or bad this type of complexity is?
- According to how I describe it, am I right in my complexity calculations? If not what can I change?
- Do you think my idea is bad, average or good? Do you have any suggestions on something I could think differently?
PS. I found one source that said $O(\log^2n)$ is still fast, but that $m$ changes everything. Also, this is the first time I'm properly working with algorithms and complexity and it's a new concept for me that's why I'm looking to understand them better here. Thanks for your help!