Majority Element Algorithm using randomization

[Ananyapam7]

This is O(n):

• New algorithm
• Update to an existing algorithm
• Error
• Proposal to the Repository

Details:

The current implemented algorithm which finds the majority element of an array is the Moore-Voting algorithm. However, there are a few other ways to solve this problem which I believe must be a part of this repository. One of them is using a randomized algorithm. On average it has the same runtime, but when the size of the array increases exponentially, this algorithm is much much faster probabilistically.

The majority element of a vector is an element which occurs with a frequency more than floor(n/2). So you have more than a 50% chance of picking out the majority element in your first try if you pick any element randomly.

Suppose you don't find the majority element in your first try. You can then pick a random element again and check if it is a majority element. You do this until you eventually find the majority element.

The algorithm is verifiably correct because we ensure that the randomly chosen value is the majority element before ever returning. I believe that this algorithm must be a part of this repository

[Ananyapam7]

I have submitted the pull request #6607 for this issue as a part of the Hacktoberfest 2022.