Counting letter frequency in array in O(1) with hash function 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?
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.