CODEWITHSUNDEEP
arraysalgorithm
user624438
user624438

Reputation: 31

Las Vegas algorithm runtime analysis

In an array of n elements, if n/2 are repeated elements and the rest are distinct, we could use the Las Vegas algorithm to get the repeated element in o(logn) time.

There is this other question which says: What is the minimum number of repetition required to make this algo o(logn) i.e (n/k repeated elements where k=?) and what's the runtime if the repeated element is root(n)?

My result says it's not o(logn) if the repeated element is root(n), but I can't find a loose bound for this problem using the Las Vegas algorithm. Help will be appreciated.

Upvotes: 3

Views: 1456

Answers (1)

123
123

Reputation: 66

"Las Vegas" isn't an algorithm; it's a type of algorithm. The obvious algorithm is to sample pairs of elements uniformly at random until they match. When the array has an element repeated n/2 times, the probability of success for each pair is ((n/2)/n)((n/2-1)/(n-1)) = 1/4 - O(1/n), so the expected running time is 1/(1/4 - O(1/n)) = 4 + O(1/n) = O(1) sampled pairs.

Since this is probably homework, you get to figure out how to adjust the analysis for differing numbers of repetitions.

Upvotes: 2

Related Questions