I kinda hate it how all the K advocacy always uses old-style languages with small stdlibs, _and_ always ignores the complexity.. How about matlab (which does have "unique" in stdlib), python/numpy or even R?
library(data.table)
v <- rbindlist(list(
data.table(e1=1, string='one'),
data.table(e1=1, string='two'),
data.table(e1=1, string='three'),
data.table(e1=1, string='one'),
data.table(e1=1, string='four'),
data.table(e1=1, string='two'))
)
v[, list(counter= sum(e1)),by= string]For K, I think the solution is to find unique first (nlog(n)), the for each unique value go over the list and find how many input values match (multiply by n). That's O(n^2 * log(n)), even worse than I wrote initially.
Your analysis of the algorithm you've described is also wrong: it would be O(n*log(n) + n^2), or O(n^2), because the second part loops over unique elements and not operations performed by unique.
In the random-access model, hash table construction/lookup is O(n) average case for n elements, if the elements have bounded size. More generally, it's linear in the total size of the input. If the strings are very long it can take a while to hash and compare them, but there's never a log(n) factor. Maybe you're confusing this with results from comparison sorting?
Both solutions are O(n) with the assumptions of random-access memory and bounded string size (or hash/comparison time), which I consider to be pretty standard.