some element of is nonzero. Suppose that the element . By the definition of matrix multiplication, we have: . For some constant . Using Bayes' theorem, we can partition over : We use that: Plugging these in the equation (), we get: Therefore, This completes the proof. Ramifications Simple algorithmic analysis shows that the running time of this algorithm is (in big O notation). This beats the classical deterministic algorithm's runtime of (or if using fast matrix multiplication). The error analysis also shows that if the algorithm is run times, an error bound of less than can be achieved, an exponentially small quantity. The algorithm is also fast in practice due to wide availability of fast implementations for matrix-vector products. Therefore, utilization of randomized algorithms can speed up a very slow deterministic algorithm. Freivalds' algorithm frequently arises in introductions to probabilistic algorithms because of its simplicity and how it illustrates the superiority of probabilistic algorithms in practice for some problems. See also Schwartz–Zippel lemma References Freivalds, R. (1977), “Probabilistic Machines Can Use Less Running Time”, IFIP Congress 1977, pp. 839–842. Articles containing proofs Matrix theory Randomized algorithms Matrix multiplication algorithms