Let a be an array of n positive integers. If a particular value, v, occurs more than n/2 times in a then we say that this value dominates a. Obviously, for any array, a, there is at most a single value that dominates a (which we call it SVD). For example, 7 is the SVD for the array
[7, 7, 9, 3, 2, 7, 7],
but the array
[7, 7, 9, 3, 2, 7]
has no SVD.
The SVD problem is: given an array, a, of positive integer values, find the single value dominating a, if it exists, or report that one does not exist otherwise.
1. Design an algorithm for solving the SVD problem whose worst-case run-time complexity is O(n2). This should be the most obvious approach involving nested iteration over the array, and not use sorting nor any secondary data structure.
2. Design an algorithm for solving the SVD problem whose worst-case run-time complexity is O(nlog(n)). This can employ a secondary data structures and/or assume standard algorithms are available (i.e. those available in Java).
3. Design an algorithm for solving the SVD problem whose space complexity and worst-case run-time complexity are both O(n). The best way of solving this does not require any secondary data structure, although partial marks will be given for approaches that do so, assuming the time complexity is O(n).
4. Implement and test your algorithm for questions 1, 2 and 3. Design an experiment to test the timing, and produce graphs for each approach that experimentally verify the worst case run time complexity of each approach.