What are randomized algorithms?

Randomized algorithms

Randomized algorithms use random numbers or choices to decide their next step. We use these algorithms to reduce space and time complexity. There are two types of randomized algorithms:

  1. Las Vegas algorithms

  2. Monte-Carlo algorithms

Las Vegas algorithms

Las Vegas algorithms always return correct results or fail to give one; however, its runtime may vary. An upper bound can be defined for its runtime.

Quicksort

Quicksort is a sorting algorithm that uses the divide and conquers technique. A pivot point is selected randomly from an array which is then partitioned so that all elements lesser than the pivot are placed on its left, and more significant elements are placed on its right. These steps are carried out recursively until the whole array is sorted.

Example

Note: Purple indices are selected as the pivot point.

The last index is selected as the pivot point in the example above. In the worst case, the pivot point selected is the maximum or minimum element.

def partition(array, start, end):
  pivot = array[end]
  i = start
  for j in range (start, end):
    if array[j] < pivot:
      array[i], array[j] = array[j], array[i]
      i = i+1
  array[i], array[end] = array[end], array[i]
  return i;
def QuickSort (array, start, end):
  if start < end:
    pivotelement = partition(array, start, end)
    QuickSort(array, start, pivotelement - 1)
    QuickSort(array, pivotelement + 1, end)
array=[23,11,43,22,34,42,1]
#print(len(array))
QuickSort(array, 0, len(array)-1)
print(array)

Explanation

  • Line 2: The last element in the array is selected as the pivot point.

  • Lines 5–7: If the element array[j] is lesser than the pivot, replace it with array[i], which points to an element more significant than the pivot.

  • Line 8: Swap pivot with array[i] as it is the first array element more significant than the pivot point.

  • Line 9: Return index of pivot.

  • Line 13: Find the pivot point and place it so that all elements lesser than the pivot are placed on its left, and more significant elements are placed on its right.

  • Lines 14–15: Apply QuickSort on both sides of the pivotelement.

Monte-Carlo algorithms

The Monte-Carlo algorithms work in a fixed running time; however, it does not guarantee correct results. One way to control its runtime is by limiting the number of iterations.

Freivalds’ algorithm

Freivalds’ algorithm is used to verify the result of matrix multiplication in O(n2n^2) time. In this algorithm, three nxn matrices, A, B, and C, are given input, where C = AB. The algorithm generates a random matrix r of size n and computes AxBr−CrA x Br - Cr to verify the value of C. If the result is equal to zero, it means that C is correct, and the result is considered incorrect for non-zero values.

Through Freivalds’ algorithm, we can control the runtime; however, it may produce erroneous results. For example, the result can be zero even though C is sometimes incorrect.

Example

Note: The resultant matrix [0,0] verifies the given input matrix C.

import numpy as np
import random
def Freivald(A, B, C):
  r = ([random.randint(0,50)],[random.randint(0,50)])
  Br = np.dot(B,r)
  Cr = np.dot(C,r)
  answer = np.dot(A, Br) - Cr
  return answer
A = ([3,6],[2,1])
B = ([4,5],[3,6])
C = np.dot(A,B)
result = Freivald(A,B,C);
print (result)

Explanation

  • Line 5: Generate a random matrix r of size [n][1].

  • Lines 6–7: Calculate Br and Cr using the built in matrix multiplication function, np.dot(matrix1,matrix2).

  • Line 8: Calculate ABr−CrABr - Cr.

  • Lines 14–15: Matrix C is correct if the result is equal to [0,0].

Free Resources

Copyright ©2025 Educative, Inc. All rights reserved