I'm trying to analyze an algorithm's behavior and, in short words, these are the characteristics about it that are relevant for this question:
- It generates vectors from a random source.
- There is a total of up to $2 ^ {n - 1}$ of those vectors , $y_i$.
- The algorithm is repeated until all those possible vectors are gathered.
- In this repetition process, there is a chance failing to get a proper value. It's a Las Vegas algorithm, so we know when that happens.
- The probability of gathering an invalid value for $y_i$ can be expressed as:
$$ P(\text{failure}) = \sum_{k=i} ^ {n - 1} 2^{-k} $$
As you can see, when $n$ tends to infinity, the probability of failure getting the last value ($y_{2 ^ {n - 1}}$) is 1.
I'm absolutely lost about how can I express its complexity. Could you please provide me with some guidance?