What is With High Probability on Probabilistic Algorithms?
An event happens with high probability with respect to a parameter $n$ if it happens with probability $p_n$ and $\lim_{n\to\infty} p_n = 1$. Usually the parameter $n$ is clear from the context. In this case, for example, it is probably the number of elements in the list.

The definition of "with high probability" in the lecture notes is even more specific, specifying how fast $p_n$ should converge to $1$: an event happens with high probability if it happens with probability $p_n \geq C/n^\alpha$ for some $C,\alpha&gt;0$. For example, if you choose a random number from $\{0,\ldots,n\}$ then it is non-zero with high probability since the probability that it is non-zero is $1-1/(n+1) \geq 1-1/n$ (so in this case $C=\alpha=1$).