I came across the problem to bound the computational complexity of the Monte Carlo rejection sampler, sampling from a proposal distribution $q_T$ rather than the target distribution $p_T$. The two distributions are related by $sup_k \frac{p_T}{q_T} \leq M < \infty$ where $M$ is a known constant. At first glance, I would believe that the number of samples depends only on $M$, specifying how many samples are needed until one is accepted. Ergo, the computational complexity of the Monte-Carlo rejection sampler is bounded by $\mathcal{O}(M)$ but I am not sure if that is true.
Any hint is highly appreciated.