Let's start with a problem statement:

given an array of length $n$ with numbers $1$ through $n$ (inclusive), consider the following steps:

  1. Select a random number $k$ in range $[1, n]$.
  2. Set $a[k] = q$.
  3. If there exists element $p$ in $a$ such that $p \ne q$, go to step 1, otherwise end.

So, basically we are going to randomly pick elements in the array and set them to some predefined value until every element in the array is set to this value. What is the time complexity of such algorithm? please explain your answer.


closed as unclear what you're asking by Juho, Evil, Yuval Filmus, David Richerby, Rick Decker Dec 2 '16 at 3:19

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • 1
    $\begingroup$ This is a well-known problem that comes up in different guises. Where did you get stuck in solving the problem? $\endgroup$ – Juho Nov 30 '16 at 17:25
  • $\begingroup$ makes sense to think about Average-case complexity $\endgroup$ – Apiwat Chantawibul Nov 30 '16 at 19:32

This is the coupon collector's problem. You can find its analysis in introductory textbooks on probability theory, among other sources.


The complexity is non deterministic. It depends on how the random value is being picked. In this case we can only determine the expected value to complete the task but not complexity.


Not the answer you're looking for? Browse other questions tagged or ask your own question.