Any algorithm better that O(N*logN) for a problem of finding student with largest average score in a list of N scores of the form StudentID, score
You are on a good path, but seem to be confused for no reason. After step 2 you have created an array with average scores. This is a worst case O(N) size array. What is the complexity of finding the highest average score now? Do you need to sort the array?