Consider the problem of computing the minimum of a set of $n$ distinct numbers. We choose a permutation uniformly at random (i.e., each of the n! permutations of $\left \langle 1,....,n \right \rangle$ is chosen with probability $(1/n!)$ and we inspect the numbers in the order given by this permutation. ... number of times MIN is updated? $O (1)$ $H_{n}=\sum ^{n}_{i=1} 1/i$ $\sqrt{n}$ $n/2$ $n$

asked
Nov 19, 2015
in Algorithms
makhdoom ghaya
834 views