(1)

Let be the values of after processing .         (2)

We use induction proof: If a list has the number of varieties of user IDs being at most one then .

Base case: , so when .

Induction step: At the th iteration, we assume that . We prove that if , .

If is empty then , so .

In the case is not empty, is added to if it is already included in , so . If is not already included in , it will not be added to , moreover one number of will be excluded in , so .

So the statement follows.

(3)

If exists then frequencies of must be larger than , which implies .

So if numbers in the list are not , then they are guaranteed to be removed all in step ii-(b) by the corresponding numbers (or by other numbers of different values).

If the numbers in list are , then it is guaranteed to have at least one number left for step iii as the total number of values different from must be less than the frequency of by definition.

So the statement follows.

(4)

L = -1

while a != -1:

if L == -1:

L = a

else:

if L != a:

L = -1