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?