{
  "id": "enwiki-001375384950",
  "slug": "las-vegas-algorithm",
  "title": "Las Vegas algorithm",
  "qid": "",
  "lead": "In computing, a Las Vegas algorithm is a randomized algorithm that always gives correct results; that is, it always produces the correct result or it informs about the failure. However, the runtime of a Las Vegas algorithm differs depending on the input. The usual definition of a Las Vegas algorithm includes the restriction that the expected runtime be finite, where the expectation is carried out over the space of random information, or entropy, used in the algorithm. An alternative definition requires that a Las Vegas algorithm always terminates (is effective), but may output a symbol not part of the solution space to indicate failure in finding a solution. The nature of Las Vegas algorithms makes them suitable in situations where the number of possible solutions is limited, and where verifying the correctness of a candidate solution is relatively easy while finding a solution is complex. Systematic search methods for computationally hard problems, such as some variants of the Davis–Putnam algorithm for propositional satisfiability (SAT), also utilize non-deterministic decisions, and can thus also be considered Las Vegas algorithms.",
  "body": "In computing, a Las Vegas algorithm is a randomized algorithm that always gives correct results; that is, it always produces the correct result or it informs about the failure. However, the runtime of a Las Vegas algorithm differs depending on the input. The usual definition of a Las Vegas algorithm includes the restriction that the expected runtime be finite, where the expectation is carried out over the space of random information, or entropy, used in the algorithm. An alternative definition requires that a Las Vegas algorithm always terminates (is effective), but may output a symbol not part of the solution space to indicate failure in finding a solution. The nature of Las Vegas algorithms makes them suitable in situations where the number of possible solutions is limited, and where verifying the correctness of a candidate solution is relatively easy while finding a solution is complex. Systematic search methods for computationally hard problems, such as some variants of the Davis–Putnam algorithm for propositional satisfiability (SAT), also utilize non-deterministic decisions, and can thus also be considered Las Vegas algorithms. int getRandomInteger(int n) { Random rand = new Random(); return rand.nextInt(n); } // Las Vegas algorithm, assuming a is array of length n. // Goal: return a correct index k such that a[k] == 1. int lasVegasAlgorithm(int[] a) { int n = a.length; while (true) { int k = getRandomInteger(n); if (a[k] == 1) { return k; } } } As mentioned above, Las Vegas algorithms always return correct results. The code above illustrates this property. The goal is to find an index in the array a that contains the value 1. A variable k is generated randomly; after k is generated, k is used to index the array a . If this index contains the value 1, then k is returned; otherwise, the algorithm repeats this process until it finds 1. Although this Las Vegas algorithm is guaranteed to find the correct answer, it does not have a fixed runtime; due to the randomization, it is possible for arbitrarily much time to elapse before the algorithm terminates. some t max such that P(RT A,x ≤ t max ) = 1. approximately complete Las Vegas algorithms solve each problem with a probability converging to 1 as the run-time approaches infinity. Thus, A is approximately complete, if for each instance x, lim t→∞ P(RT A,x ≤ t) = 1. essentially incomplete Las Vegas algorithms are Las Vegas algorithms that are not approximately complete. Approximate completeness is primarily of theoretical interest, as the time limits for finding solutions are usually too large to be of practical use. In case of Type 3, its run-time behavior can only be represented by the run-time distribution function rtd: R → [0,1] defined as rtd(t) = P(RT ≤ t) or its approximation. The run-time distribution (RTD) is the distinctive way to describe the run-time behavior of a Las Vegas algorithm. With this data, we can easily get other criteria such as the mean run-time, standard deviation, median, percentiles, or success probabilities P(RT ≤ t) for arbitrary time-limits t. def randomized_quicksort(a: list[int]) -> None: if len(a) == 1: return A # A is sorted. else: i: int = random.randrange(1, len(a)) # Will take a random number in the range [1, len(a)) x: int = a[i] # The pivot element # Partition a into elements x, as shown in the figure above. # Execute Quicksort on a[1 : i- 1] and A[i + 1 : n]. # Combine the responses in order to obtain a sorted array. 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 immediately obvious, as the runtime depends on which element is picked as a pivot. The worst case is Θ(n 2 ) when the pivot is the smallest or the largest element. T(n)=T(0)+T(n-1)+\\Theta (n) T(n)=\\Theta (1)+T(n-1)+\\Theta (n) T(n)=T(n-1)+\\Theta (n) T(n)=\\Theta (n^{2}) However, through randomization, where the pivot is randomly picked and is exactly a middle value each time, the QuickSort can be done in Θ(nlogn). T(n) \\leq 2*T(n/2) + \\Theta(n) T(n) = \\Theta(n\\log(n)) 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 2 ), the average-case runtime is Θ(nlogn). It turns out that the worst-case does not happen often. For large values of n, the runtime is Θ(nlogn) 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(logn) with O(n) times taken each level of recursion. 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. \\textsf{ZPP} = \\textsf{RP} \\cap \\textsf{co-RP} which is intimately connected with the way Las Vegas algorithms are sometimes constructed. Namely the class RP consists of all decision problems for which a randomized polynomial-time algorithm exists that always answers correctly when the correct answer is \"no\", but is allowed to be wrong with a certain probability bounded away from one when the answer is \"yes\". When such an algorithm exists for both a problem and its complement (with the answers \"yes\" and \"no\" swapped), the two algorithms can be run simultaneously and repeatedly: run each for a constant number of steps, taking turns, until one of them returns a definitive answer. This is the standard way to construct a Las Vegas algorithm that runs in expected polynomial time. Note that in general there is no worst case upper bound on the run time of a Las Vegas algorithm. // Las Vegas algorithm int lasVegasAlgorithm(int[] a) { int n = a.length; while (true) { int k = getRandomInteger(n); if (a[k] == 1) { return k; } } } // Monte Carlo algorithm int monteCarloAlgorithm(int[] a) { int n = a.length; for (int i = 0; i Since Las Vegas does not end until it finds 1 in the array, it does not gamble with the correctness but run-time. On the other hand, Monte Carlo runs 300 times, which means it is impossible to know that Monte Carlo will find \"1\" in the array within 300 times of loops until it actually executes the code. It might find the solution or not. Therefore, unlike Las Vegas, Monte Carlo does not gamble with run-time but correctness.",
  "categories": [
    "23118434",
    "23603337",
    "24623845",
    "29176587"
  ],
  "license": "CC BY-SA 4.0",
  "source_uri": "https://en.wikipedia.org/w/index.php?oldid=1375384950",
  "content_hash": "",
  "created_at": null,
  "updated_at": 1789645791.0,
  "claims": [],
  "contradictions": [],
  "confidence": 0.6,
  "csl": {
    "id": "enwiki-001375384950",
    "type": "webpage",
    "title": "Las Vegas algorithm",
    "author": [
      {
        "family": "Anticloud FZ LLE",
        "literal": "Anticloud FZ LLE"
      }
    ],
    "container-title": "encyclopegia.org",
    "publisher": "Anticloud FZ LLE",
    "publisher-place": "Dubai, United Arab Emirates",
    "URL": "https://encyclopegia.org/a/las-vegas-algorithm",
    "issued": {
      "date-parts": [
        [
          2026,
          11,
          15
        ]
      ]
    },
    "accessed": {
      "date-parts": [
        [
          2026,
          11,
          15
        ]
      ]
    },
    "license": "CC BY-SA 4.0",
    "DOI": "eo1:enwiki-001375384950",
    "isBasedOn": "https://en.wikipedia.org/w/index.php?oldid=1375384950",
    "note": "Immutable snapshot enwiki-001375384950"
  }
}