Counting letter frequency in array in O(1) with hash function

Question

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?

Answer 1

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.