1
$\begingroup$

I want to calculate the frequency of each character in an array. (e.g ['a', 'b', 'o', 'p']

There are several ways to do this:

  • A Simple brute-force over the array would need $O(n^2)$ time and $O(n)$ space

  • Sorting the array first and serial counting the characters is a better solution with $O(n \log n)$ time and $O(n)$ space

  • But the optimal solution is... using hash tables with $O(1)$ access time. The thing is, I do not quite understand why the complexity is supposed to be $O(1)$ and not $O(n)$. After all, we still have to iterate over the array. For example

    def fCount(A):
    
      frequencies = new hashTable()
    
      for character in A: // This is O(n) !!!
          frequencies(character) += 1  
    

Yes, the access time is $O(1)$ but in order to create the hash table, you still need $O(n)$ time and space.

So why is this supposedly $O(1)$ time and $O(1)$ space?

$\endgroup$
1
  • 1
    $\begingroup$ Since there are only 256 characters. Even the brute force will take $O(n)$ time. $\endgroup$ – Inuyasha Yagami Jan 19 at 19:46
3
$\begingroup$

The complexity is $O(n)$. What is $O(1)$ is the time it takes to access a cell in the hash table.

By the way, assuming that each character is a byte, you can just use a plain old array of length 256.

$\endgroup$
1
  • $\begingroup$ But... unicode... or non-ASCII/Latin1 encodings... $\endgroup$ – D. Ben Knoble Jan 19 at 23:19

Your Answer

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

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