I watched lecture from MIT about Skip List. Overall, I understand the material, but one thing. What is "with-high-probability"? I really don't get it at all. I've seen the lecture notes but still didn't get it.
They just said, "Event $E$ occurs with high probability (w.h.p.) if, for any $\alpha\geq1$, there is an appropriate choice of constants for which $E$ occurs with probability at least $1 − O(1/n^\alpha)$".
Something from algorithmist.com didn't help, either.
What is $\alpha$ and what is $1 − O(1/n^\alpha)$? Not understanding this thing make me confused of the analysis of why "With high probability, every search in an $n$-element skip list costs $O(\lg n)$".