What is the complexity of randomly selecting a non-null element from an array that has nulls?

Question

Say I have an array where I want to randomly select elements from the array, but some of the array elements are null, like this:

[0, 1, 3, null, 3, 2, null, 9, 12]

If I select them at random (with a good, unbiased random number generator), and land on a null, then I select again at random until I find a non-null element. I do it this way to avoid introducing bias into my selections.

The question is: what is the time complexity (in big-O notation, or a more appropriate notation of time-complexity) of such a selection?

Clearly, if all the elements are null, then it will never complete, and if none of the elements are null, then it's O(1), but it's unclear to me how to express the values in between.

I'm aware that a different way of organizing the array would avoid holes, and then it could always be O(1): I'm not asking how to implement it better, I'm asking how to express this kind of complexity.

Answer 1

As you noted, in the worst case this algorithm never terminates and therefore T(n) is undefined (or infinity).

You may be more interested in average-case time complexity, which is used more often than worst-case complexity to describe randomized algorithms such as yours.