Two techniques are used to find the mode of integer test scores between 0 and 100:
Method A: Insert every score into a sorted array, and then scan the array to find the longest sequence of equal values.
Method B: Use a count array of size 101, increment the count corresponding to each score, and then find the index containing the largest count.
Determine the time and space complexities of both methods using Big-O notation in terms of n.
Ans.
| Method | Time Complexity | Space Complexity |
| A — Sorted-array insertion | O(n2) | O(n) |
| B — Count array | O(n) | O(1) |
Based on their Big-O bounds, Method B is preferable because it is better in both time and auxiliary space.
💡 Explanation:
Method A: Each of the n scores must be inserted into its correct position in the sorted array. A single insertion may require shifting up to n existing elements.
Therefore, building the sorted array requires:
n insertions × O(n) shifting work = O(n2)
The final scan for the longest run takes O(n), but O(n2) dominates O(n). The stored scores require an array of size n, so the space complexity is O(n).
Method B: The count array has exactly 101 positions, one for every possible score from 0 through 100.
Processing all scores takes one pass:
n scores × O(1) update per score = O(n)
Scanning the 101 counters takes O(101) = O(1) time because the score range is fixed. The same reasoning makes the count array's space usage O(1): its size does not grow when n increases.
Hence, Method B completes the task in O(n) time with O(1) auxiliary space, making it more efficient than Method A.
Memory tip: When values come from a small, fixed range, a counting or bucket array can often replace sorting and reduce the running time.