2
$\begingroup$

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:

  1. Can you give me an idea of how good or bad this type of complexity is?
  2. According to how I describe it, am I right in my complexity calculations? If not what can I change?
  3. 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!

Improve this question
$\endgroup$
9
  • 1
    $\begingroup$ Are the integers representing each user guaranteed to form consecutive numbers, or are they arbitrary? $\endgroup$
    – Russel
    Commented May 13, 2022 at 15:31
  • $\begingroup$ Also, how did you come up with that running-time? If there are $m$ entries in the file but only $n$ users, then you will perform $m$ queries to the AVL tree. A query can take at most $O(\log n)$ so that's just $O(m \log n)$. However, do not forget that you will also do $n$ inserts to the tree, which takes $O(n \log n)$. The running-time will be $O((n+m) \log n)$, which will still be $O(m \log n)$ anyway given that $m \ge n$. $\endgroup$
    – Russel
    Commented May 13, 2022 at 15:39
  • $\begingroup$ @Russel It doesn't specify, but I'd assume that each user has their own integer, so if there's 3 users with codes 1,2,3 then one day the file would only include 1s and 3s if 2 didn't use the survice but was registered. So for larger numbers (say a million) the numbers would look pretty random and arbitrary. $\endgroup$
    – Tita
    Commented May 13, 2022 at 15:44
  • $\begingroup$ @Russel As far as the running-time goes, my thought process was that I have m iterations (as I have to get each of the m codes separately), checking if a key exists in the tree takes $O(logn)$ according to my notes and then adding it in the tree (if key = code) doesn't exist would also take $O(logn)$. Wouldn't that then make $O(m)$ iterations x $O(logn)$ checks x $O(logn)$ at most insertions? I'm still learning so this might be completely wrong. Also, I;m having trouble understanding why you say I'll make $n$ inserts in the tree. Should I not be checking for an existing key at all? $\endgroup$
    – Tita
    Commented May 13, 2022 at 15:49
  • 2
    $\begingroup$ If you query before you insert, then the total time is the time for query plus the time for insert. You do not multiply them. I said you will perform $n$ inserts only, because you are checking first if the key exists before you insert, and since there are only $n$ unique keys, then there are $n$ inserts. Btw, you actually do not need the checking since a SortedMap guarantees unique keys only, so adding a duplicate key will replace the previous key but that does not affect the correctness. And lastly, just use a SortedSet instead of a SortedMap. $\endgroup$
    – Russel
    Commented May 13, 2022 at 16:01

1 Answer 1

Reset to default
1
$\begingroup$

Suppose there are $m$ elements in a sequence containing $n$ distinct elements, and the distinct elements are stored in an AVL tree. Then, each of the $m$ Lookups will take $O(\log n)$ time. Each of the $n$ inserts will take $O(\log n)$ time, for a total cost of $O(m \log n + n \log n) = O(m \log n)$.

However, since this problem requires a lot of lookups (to check whether an existing element has already been seen in the sequence), hash tables would be a good data structure to use. Then, each lookup would take $O(1)$ expected time, and each insert would take $O(1)$ time. The total cost would be $O(m)$ expected time, which is blazingly fast.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.