# 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

Question: Suppose you are a given a csv with N lines of the form StudentID, score. Multiple lines can have same student-ID. Find the student with maximum average score

I can't think of any way to make it faster than O(N*logN).

1. Maintain a hash-table that keeps track of STudentID = Key and Value being an object with sum of scores and number of scores seen with that studentID --> O(N)

2. Create an array with values in hash table, maybe convert each entry into average while doing so

3. Sort it worst-case N(logN), all entries belong to same student

Is there any way to do it faster?

• Note that hashtables don't usually have $O(1)$ worst-case performance. – Raphael Sep 28 '16 at 6:14
• Finding maximums is trivially in $O(n)$. I don't get what your problem is. – Raphael Sep 28 '16 at 6:14

• you can calculate averages online, instead of computing it at the end. You need to maintain the count and average. For every score update and before updating the count, new_avg = (old_avg*count + score)/(count + 1). Then update the count.