Parallized algorithm for getting the frequencies of numbers in an array
It is common problem in parallel computing. Many parallel framework have &quot;reduction operator&quot; for such processing. Idea is simple.
Use separate local copies of F[A[i]] in each threads. Calculate frequency in parallel for each sub-array block in parallel. Now since each thread is updating only its local copy of frequency array F[A[i]], no mutex is required. After the completion of all threads, join all the per thread F[[A]] array's into a single application array, i.e., reduce. You will get almost O(n/p) time complexity. The actual time complexity will depend on Size of your array (larger, the better) and the number of threads (creating and joining threads takes time).