0
$\begingroup$

I would like to calculate the time complexity of an algorithm which returns the number of accesses of a website and the number of different users who entered. Each user is represented by a unique integer. (Suppose that we're given the method getNextAccess() which returns the next user's integer in $O(1)$ time.)

My solution was to create a Hash Table with each user's integer as key and two integer variables totalCount and DisCount. Then (in pseudo-code):

if(getNextAccess does not return null){
   if(HashMap contains this integer){
      totalCount++;
   }
   else{
      HashMap.put(this integer);
      totalCount++;
      disCount++;
   }
}

When it comes to time complexity, since HashMap can search and insert in $O(1)$ and we repeat this process for $n$ accesses, the final complexity would be $O(n)$.

Is this result correct or does the complexity also depend on the number $m$ of different users?

$\endgroup$
  • $\begingroup$ You shouldn't blindly assume constant time search and insert in the worst case for a hash table. See for instance this question for more. $\endgroup$ – Juho May 5 at 11:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.