# Computational complexity of sampling from discrete and continuous distributions? [closed]

What is the computational complexity of sampling from any of these cases? I mean the computational complexity of the most efficient existing algorithm, not a possible algorithm or a lower bound.

1. Finite discrete probability distribution $$p_1, ..., p_N$$: I think this is $$O(\log N)$$. I tested sampling using python function np.random.choice and the log plot was linear. Also, I think this is true based on this paper: https://people.mpi-inf.mpg.de/~kbringma/paper/2012ICALP.pdf

2. A continuous distribution with closed-form pdf and CDF, for example, exponential distribution. From python implementation, it seems to be $$O(1)$$ but I'm not sure how to test that.

3. A continuous distribution with closed-form pdf while CDF is not closed form, for example, normal distribution. It seems to be $$O(1)$$

What about sampling from truncated versions of these distributions? Could anyone also suggest reference/references on this topic?

• O(1) for discrete distributions: see keithschwarz.com/darts-dice-coins for a very nice discussion. Commented May 5, 2021 at 9:38
• The complexity depends on the algorithm. A huge number of algorithms are extant, with many specialized algorithms developed for various distributional families.
– whuber
Commented May 6, 2021 at 14:05