Let's start with a problem statement:
given an array of length $n$ with numbers $1$ through $n$ (inclusive), consider the following steps:
- Select a random number $k$ in range $[1, n]$.
- Set $a[k] = q$.
- 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.