Якщо складність цього алгоритму дорівнює o(n), а попередня складність Θ(n log(n)), то чому o(n), що мала б бути простішою і швидшою за перший, виявилася повільнішою?

Ймовірно тому що push до frequencies в даному випадку не є завжди О(1). frequencies буде перерозподілятись з O(n) витратами на копіювання на визначених двіжком межах довжини. Прискорення буде відчутним якщо створити array з одразу заданою довжиною.