Let's say we're comparing the time complexity of search function in hashmap vs trie.
On a lot of resources I can find, the time complexities are described as Hashmap get: O(1) vs Trie search: O(k) where k is the length of chars in the string you want to search.
However, I find this a bit confusing. To me, this looks like the sample size "n" is defined differently in the two scenarios.
If we define n as the number of characters, and thus are interested in what's the complexity of this algorithm as the number of characters grow to infinity, wouldn't hashmap get also have a time complexity of O(k) due to its hash function?
On the other hand, if we define n as the number of words in the data structure, wouldn't the time complexity of Trie search also be O(1) since the search of the word doesn't depend on the number of words already stored in the Trie?
In the end, if we're doing an apple to apple comparison of time complexity, it looks to me like the time complexity of Hashmap get and Trie search would be the same.
What am I missing here?
Yes, you are absolutely correct.
What you are missing is that statements about an algorithm's complexity can be based on whatever input terms you like. Outside of school, such statements are made to communicate, and you can make them to communicate whatever you want.
It's important to make sure that you are understood, though, so if there is a chance for confusion about how the n in O(n) is measured, or any assumed constraints on the input (like bounded string size), then you should just specify that explicitly.