In an array of n elements, if n / 2 are repeating elements and the rest are different, we could use the Las Vegas algorithm to get the repeating element in o (logn) time.
There is another question that says: "What is the minimum number of repetitions required to create this algorithm o (logn), i.e. (n / k repeating elements, where k =?), And what is the runtime if the repeating element is root ( P)?
My result says that it is not o (logn) if the repeating element is root (n), but I cannot find a loose binding for this problem using the Las Vegas algorithm. Help will be appreciated.
source
share