Time complexity of this while loop

Question

So, i would like to know the time complexity of the following codes:

x = (float) rand() / rand();   // T(4)

while (x >= 0.01)   // T(?)
{
    x *= 0.8;  // T(?) x T(2)
}

Assuming that all the basic operations are perfomed once, is the best case T(1) - constant time? Since, that might only happen when the random x generated is <= 0.01.

What about the average case? Is it T(?) x T(1) / 2?

Thanks a lot!

Answer 1

Worst case, if the second call to rand() returns 0 and the first call doesn't, you get a floating point division by zero, and if you are using standard IEEE 754 arithmetic, the result is +infinity. In that case, the loop will run forever.

If you changed your code to exclude that case, and exclude the case that rand () might return a 128 bit integer, then for any implementation the size of x is limited, so the number of multiplications by 0.8 is limited, so the runtime is O (1).

Answer 2

This answer refers to a version of the question in which $x$ is sampled by dividing two random numbers.

As mentioned by Rick Decker's answer, given $x$, we can approximate the running time by $O(\max(\log x,1))$. Assuming that rand returns a random number in $[0,1]$, the running time should be proportional (up to an additive constant) to $$ \int_0^1 \int_0^1 \max(\log \tfrac{x}{y},0) \, dx \, dy. $$ Let us start by computing the inner integral: $$ \int_0^1 \max(\log \tfrac{x}{y},0) \, dx = \int_y^1 \log \tfrac{x}{y} \, dx = (1-y)\log y + \int_y^1 \log x \, dx = \\ -(1-y)\log y + \left. x(\log x-1) \right|_y^1 = -(1-y)\log y-1-y(\log y-1) = \\ y-\log y-1. $$ Integrating this over $y$, we get $$ \int_0^1 (y-\log y-1) \, dy = \left. \tfrac{1}{2} y^2 - y\log y \right|_0^1 = \frac{1}{2}. $$ This shows that in this idealized setting, the expected running time is $O(1)$ (rather than infinity, which could also have been the case).

Answer 3

In general, the time taken by this snippet is mainly governed by how many times the loop iterates. In other words, how many times will you need to multiply $x$ by $0.8$ to get a result less than $0.01$?

In other words, for a fixed $x$, what $n$ value will ensure that $(0.8)^nx<0.01$?