AP CS Free Response AB-2, part c

The correct answer depends on whether a HashMap or 
TreeMap has been created for voteCount and whether
a HashSet or TreeSet has been created locally to return
as the result of the method candidatesWithMost.

If HashMap and HashSet are used, then the complexity for
candidatesWithMost is O(C). The method must iterate over the
the C entries in the map. The lookups in the map and the 
insertions into the set will be O(1).

If either TreeMap or a TreeSet, or both are used, then the
complexity for candidatesWithMost will be O(C log C). For a
TreeMap the log C factor results from the lookup in the map.
Similarly, the call to maxVotes would require an iteration 
over the Map and lookups, so it would also be O(C log C). 

If a TreeSet is used The insertion into the set for each takes 
log K time for K elements in the set. Since it is possible that 
all candidates will be tied and therefore added to the set, the 
worst case complexity is

log(1) + log(2) + ... + log(C).

Throw away the first half of this sum and estimate using the smallest
term in the rest, and you get the above sum is greater than

(C/2) log(C/2) = (C/2)(log C - log 2) which is O(C log C)

Clearly it is also less than C log C, so O(C log C is the best estimate
of the complexity.

Summary.

For HashMap and HashSet, complexity is O(C)
For HashMap and TreeSet, TreeMap and HashSet, or TreeMap and TreeSet
the complexity is O(C log C)


