# What is the time complexity of this randomized algorithm? [closed]

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 DeckerDec 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.

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

## 2 Answers

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.