What is the big O of the algorithm below?
It is not an algorithm to begin with because the operation (in the lack of a better word) you described does not fit the standard definition of what constitutes an algorithm. If it is not an algorithm, you probably should not describe it using big O notation.
As pointed out in the previous answer, the use of a PRNG is probabilistically distributed, so the time bounds would converge to a finite set of steps eventually. The rest of my answer will now assume a truly random number generating function as part of your "algorithm".
Knuth describes an algorithm in TAOCP [1, pp. 4-7] as a "finite set of rules that gives a sequence of operations for solving a specific type of problem", highlighting the characteristics of finiteness, definiteness, input, output, effectiveness.
For concision, your described operation does not:
Moreover, the lack of finiteness prompting this operation to potentially run without ever finding a 5 digit number not in the DB perfectly classifies it as an undecidable problem.
Recall that decidability means whether or not a decision problem can be correctly solved if there exists an effective method (finite time deterministic procedure) for solving it [2].
For same reason and akin to the Halting problem [3], your operation is undecidable because it is impossible to construct an algorithm that always correctly determines [see 4] a new 5 digit random number effectively. The operation described is merely a problem statement, and not an algorithm because it still needs an algorithm to correctly and effectively solve it.
You might have to consider Kolmogorov complexity [5] in analyzing your problem because it allows you to describe (and prove) the impossibility of undecidable problems like the Halting problem and Cantor's diagonal argument [6].
An answer from this post suggests the use of Arithmetic Hierarchy [7] (as opposed to asymptotic analysis) as the appropriate measure of the complexity of undecidable problems, but even I am still struggling to comprehend this.