I am not sure how to read little/big O expressions in probability theory:
What does a statement like "with probability $1-o(1)$" mean? Does it mean with high probability?
It means that the probability tends to 1 if something goes to a limit (usually the size of the sample/object goes to infinity). Without some more context nothing more can be said.