Write psuedocode to determine the number of pairs of values in an
input file that are equal. If your first try is quadratic, think again
and develop a linearithmic solution.
I found this question in a textbook and I’m not sure how to write this algorithm. My guess at first was to write it along the formula nC2 = (n(n+1))/2. Any help is appreciated.
2
I don’t want to give you the code but some hints. The first thing to pay attention is that the exercise is asking for a linearithmic solutions. This means that you algorithm may consume N log (N) time to execute where N is the number of entries (values in the file in your case).
So the basic structure of the algorithm needed seems to be one loop through all the entries and one binary search inside the loop. To do a binary search you need an ordered entry, so order it. At the end you algorithm may look something like:
- Order the file
- Loop through the file
- Binary read the file during the loop
- Check the current value in the loop and the result of the binary search