With high probability
From Algorithmist
[edit] Definition
An event occurs with high probability if, for any 
, the event occurs with probability at least 
, where cα depends only on α.
Since we can choose α, we can make the probability arbitrarily low, at a cost of time and/or space.
[edit] Example
With high probability, a set of N random numbers will contain at least O(N) evens.
What it means is: For any α, there exists a k (that doesn't depend on N), such that a set of N random numbers will contain at least k*N evens with probability , where cα depends only on α.
