Development and analysis of a linear time algorithm

Question

Develop and analyze a linear time algorithm to determine if there is an element in the list of n elements that repeats at least 10 times in the list.

How can i do this? I am posting my idea as an answer.

Answer 1

I assume the elements are comparable.

Follow the selection algorithm for: n / 10th, 2n / 10th, ..., 9n / 10th, 10 (n / 10) smallest elements ¹

These are your candidates. Check out #occurrences for each of them, and if one of them repeats the answer true at least n / 10 times. Otherwise, it is false .

Evidence:
If an element appears at least n / 10 times, it must “intersect” with k*n/10 for some k (in a sorted list) ² . Thus, this element will be selected as a “candidate”, and you will later discover (by counting) exactly how many times it will appear and return true .

If no elements are repeated n/10 times, the algorithm trivially returns false at the last step of checking each candidate.

Difficulty :
Each selection algorithm is O(n) , and runs 10 times. Also, for each candidate, a linear scan in the list is required, which also O(n) sums up in O(n) as a whole, but with scary constants.

---

Explanation

(1) The selection algorithm will find the element that will be in the index n / 10, 2n / 10, ... 9n / 10 in the sorted list, and the algorithm itself will be O(n)

(2) Let's look at an example [1,2,..,100,100,..,100] (11 times 100).
Notice that the list is sorted, and item 100 appears in: list[9*n/10] (index 9*n/10 ). The idea behind the selection algorithm is that even if you shuffle the list, select(list,9*n/10) always returns the same element - in this case 100 - since it is the 9n/10 element in the sorted list (this what the algorithm is).

Now you can see that for each element (let it be e ) that is repeated n/10 times, there is some index i , which in the sorted version of the list contains all the elements in indices i,i+1,...,i+n/10 will be e . One of these indices must be one of k*n/10 for some k (convince yourself why!). Thus, the selection algorithm on k*n/10 will give e .

Answer 2

Let me tell you a smart one-pass algorithm to find the majority element (one with a frequency above n / 2), and you should see how to adapt it:

 best = null count = 0 foreach x in list: if (count == 0) count++ best = x else if (best == x) count++ else count-- return best 

If there is a majority element, the algorithm described above will find it (one pass, constant space). Once you figure out how this works, you will see how it can be adapted to case n / 10.

Answer 3

My solution is to split the list into 10 / n groups, and each of the groups contains 10 items, and then make a randomized selection of sorting in each group, it will take O (1) * O (n), which is O (n )

Since the candidate element must be displayed in each of the n / 10 groups to satisfy the requirements, we can scan for each of the 10 elements in the first group, which takes 10 * O (n) time.

So the total time for the algorithm is O (n) + 10 * O (n), which is still O (n).

But this will not work if the items in the groups look something like this:

 1,2,3,4,5,6,7,8,9,10 11,11,11,11,11,11,11,11,11,11 ... 11,11,11,11,11,11,11,11,11,11 

My algorithm will return that such an element does not exist, but in fact 11 is an element that appears more than n / 10 times.