we have RNG which generate No. between [0.0,1000.0[
in a while loop we count to find out how long does it take to produce a No. < 1.0.
code:
n =0
while ( RNG1000() >= 1.0){
n =+
}
question: what is the O(?)
A function f of variable n is said to be big-Oh of a function g of variable n - often denoted f(n) = O(g(n)), or f in O(g) - if there exists an n0 such that for all n greater than n0, f(n) <= g(n).
Suppose our algorithm's runtime were big-Oh of some function g of n. Then there is an n0 such that for n > n0, our algorithm's runtime is less than or equal to g(n). Let us choose some fixed n' > n0 and consider what this means: it means that on input n', our algorithm is guaranteed to terminate within g(n') steps. We must have that g(n') is some number; let's call it t'. So for input n', our loop cannot take more than t' steps. But this is patently false, since - assuming that a whole loop iteration takes 1 step - the probability of iterating for more than t' steps is finite but non-zero (assuming the RNG is a true RNG). This is a contradiction, so our assumption that the runtime is big-Oh of g was wrong - that is, there is no upper bound on the runtime.
It is tempting to say that this is O(1) in terms of n, since the loop condition doesn't depend on n, but that is technically incorrect, given the above analysis. There really is no upper bound here.