Person list A is an array in which pairs of person names and scores are stored. Given a person list A and person name in A, I want to determine the score of the respective person. Prove that any comparison based algorithm that solves this problem requires Ω(log n).
Doesn't all comparison based algorithms require worst case Ω(n log n) to solve the problem?
First off, everything is Ω(1), because Ω is an asymtotic lower bound, typically used to describe best case scenarios
I assume you were talking about Big O notation for the worst case scenarios.
What you are thinking about is a comparison based sorting algorithm, which would be O(n log(n)). But we don't need to sort the whole list, we just need to find a single entry in that list, so we already know for sure that we could do a linear scan and find that entry in O(n), which is a little better than O(n log(n)).
If your entries are just randomly arranged in list A, then O(n) is the best you're going to get, you could try turning the list into a heap and binary searching O(log n) your way through it, but the BUILD-HEAP algorithm takes O(n) (Section 7.3 of "Introduction to Algorithms" by Cormen et al. Third printing 1991), so I don't think you can beat O(n).
Are you sure your not dealing with a sorted list? or that maybe list A has some kind of structure already?