Если с созданием нового массива, то можно так:
Создается новый массив (заранее или динамически), индексы которого - значения исходного массива, а значения нового массива - кол-во одинаковых значений исходного массива. Сложность такого алгоритма минимальная - O(N).

Den_diЕсли у нас тип данных DWORD то нам понадобиться создать
2^34 бийтный массив, и пробежать его весь, сначало обнулив
Не знаю какой вы имели в виду язык программирования, но поверьте, что не во всех языках надо обнулять такой массив.
Den_diДаже если это будет кеш память (всего-то 16 гигов+- сам массивчик), то времени уйдёт шчень много на небольшие массивы.
Для этого существуют динамические массивы. В некоторых языках, например, php, массив может состоять из элементов не по порядку. Т.е. например? если есть массив $arr1(), то элементы в него можно добавлять просто. Примерно так (давно на php ничего не писал):
При этом промежуточные элементы с номерами 2..11 не создаются.

Den_diВозьмём типичный размер, для которого время уже имеет значение 2^24 элементов
Что-то не совсем понял.