Editing Las Vegas algorithm (section)

== Applications ==
=== Analogy ===
Las Vegas algorithms arise frequently in [[search problem]]s. For example, one looking for some information online might search related websites for the desired information. The time complexity thus ranges from getting "lucky" and finding the content immediately, to being "unlucky" and spending large amounts of time. Once the right website is found, then there is no possibility of error.<ref>Randomized Algorithms. ''Brilliant.org''. Retrieved 23:54, October 24, 2018, from https://brilliant.org/wiki/randomized-algorithms-overview/</ref>

=== Randomized quicksort ===
<syntaxhighlight lang="python">
INPUT: 
    # A is an array of n elements
def randomized_quicksort(A):
    if n == 1:
        return A  # A is sorted.
    else:
        i = random.randrange(1, n)  # Will take a random number in the range 1~n
        X = A[i]  # The pivot element
    """Partition A into elements < x, x, and >x  # as shown in the figure above.
    Execute Quicksort on A[1 to i-1] and A[i+1 to n].
    Combine the responses in order to obtain a sorted array."""
</syntaxhighlight>

A simple example is randomized [[quicksort]], where the pivot is chosen randomly, and divides the elements into three partitions: elements less than pivot, elements equal to pivot, and elements greater than pivot. QuickSort always generates the solution, which in this case the sorted array. Unfortunately, the time complexity is not that obvious. It turns out that the runtime depends on which element we pick as a pivot.

* The worst case Θ(''n''<sup>2</sup>) when the pivot is the smallest or the largest element.

:<math>T(n)=T(0)+T(n-1)+\Theta (n)</math>
:<math>T(n)=\Theta (1)+T(n-1)+\Theta (n)</math>
:<math>T(n)=T(n-1)+\Theta (n)</math>
:<math>T(n)=\Theta (n^{2})</math><br>

* However, through randomization, where the pivot is randomly picked and is exactly a middle value each time, the QuickSort can be done in Θ(''n''log''n'').

:<math>T(n) \leq 2*T(n/2) + \Theta(n)</math>
:<math>T(n) = \Theta(n\log(n))</math>

The runtime of quicksort depends heavily on how well the pivot is selected. If a value of pivot is either too big or small, the partition will be unbalanced, resulting in a poor runtime efficiency. However, if the value of pivot is near the middle of the array, then the split will be reasonably well balanced, yielding a faster runtime. Since the pivot is randomly picked, the running time will be good most of the time and bad occasionally.

In the case of average case, it is hard to determine since the analysis does not depend on the input distribution but on the random choices that the algorithm makes. The average of quicksort is computed over all possible random choices that the algorithm might make when choosing the pivot.

Although the worst-case runtime is Θ(''n''<sup>2</sup>), the average-case runtime is Θ(''n''log''n''). It turns out that the worst-case does not happen often. For large values of ''n'', the runtime is Θ(''n''log''n'') with a high probability.

Note that the probability that the pivot is the middle value element each time is one out of ''n'' numbers, which is very rare. However, it is still the same runtime when the split is 10%-90% instead of a 50%–50% because the depth of the recursion tree will still be ''O''(log''n'') with ''O''(''n'') times taken each level of recursion.

=== Randomized greedy algorithm for the Eight queens problem ===
The [[eight queens problem]] is usually solved with a backtracking algorithm. However, a Las Vegas algorithm can be applied; in fact, it is more efficient than backtracking.

Place 8 queens on a chessboard so that no one attacks another. Remember that a queen attacks other pieces on the same row, column and diagonals.

Assume that ''k'' rows, 0 ≤ ''k'' ≤  8, are successfully occupied by queens.

If ''k'' = 8, then stop with success. Otherwise, proceed to occupy row ''k'' + 1.

Calculate all positions on this row not attacked by existing queens. If there are none, then fail. Otherwise, pick one at random, increment ''k'' and repeat.

Note that the algorithm simply fails if a queen cannot be placed. But the process can be repeated and every time will generate different arrangement.<ref>{{cite web |url = http://www.cs.man.ac.uk/~david/algorithms/randomizedAlgsSlides.pdf |title=Randomized Algorithms - a Brief Introduction |last=Barringer|first=Howard|date=December 2010 |website=www.cs.man.ac.uk |access-date=2018-12-08 }}</ref>