2
$\begingroup$

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!

$\endgroup$
  • 4
    $\begingroup$ Possible duplicate of Is there a system behind the magic of algorithm analysis? $\endgroup$ – David Richerby Jul 13 '17 at 15:49
  • $\begingroup$ It all depends on defintion. I think that rand() is bounded by constant number in your case. Then, initial x also is bounded and answer is simple. Ah, well, there is one case when this program does not halt. $\endgroup$ – rus9384 Jul 13 '17 at 16:13
  • 1
    $\begingroup$ Please edit your question to define the behavior of rand(), so knowledge of any particular programming language is not needed to be able to answer the question. Is this code fragment in C? Not everyone here may know C. We want questions to be language-independent and to be understandable even to people who don't know a particular programming language. Thank you! $\endgroup$ – D.W. Jul 13 '17 at 17:41
  • $\begingroup$ Welcome to Computer Science! What have you tried? Where did you get stuck? We do not want to just hand you the solution; we want you to gain understanding. However, as it is we do not know what your underlying problem is, so we can not begin to help. See here for tips on asking questions about exercise problems. If you are uncertain how to improve your question, why not ask around in Computer Science Chat? $\endgroup$ – Raphael Jul 13 '17 at 18:09
  • $\begingroup$ @rus9384 I have edited the definition of rand() $\endgroup$ – erwinleonardy Jul 14 '17 at 2:18
8
$\begingroup$

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).

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Assuming that the random number is changed to ((float) rand() / rand() + 0.1); Therefore, there is no dividing by zero exception. $\endgroup$ – erwinleonardy Jul 14 '17 at 2:06
  • $\begingroup$ Why is the runtime O(1)? I thought that the complexity will grow exponentially if n is a really huge number? I was guessing that it has a O(n^2) or even worse. $\endgroup$ – erwinleonardy Jul 14 '17 at 2:08
  • $\begingroup$ @erwinleonardy because x has an upper bound. $\endgroup$ – Taemyr Jul 14 '17 at 6:56
6
$\begingroup$

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).

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ His question is about average time. It is possible that x is generated as $\infty$ and then the program does not halt. But in all (constant amount) other cases the runtime is constant. Then average time is also constant (while worst case is $\infty$)? And in his code rand() returns integers in some interval, I think. $\endgroup$ – rus9384 Jul 13 '17 at 16:55
  • 1
    $\begingroup$ Even if rand returns an integer from $1$ to $N$ (or from $0$ to $N$), in the large $N$ limit we get the same result, since rand/rand is the same as (rand/N)/(rand/N), and rand/N converges in the large $N$ limit to the uniform distribution over $[0,1]$. $\endgroup$ – Yuval Filmus Jul 13 '17 at 17:04
  • 1
    $\begingroup$ I think the assumption in your answer is wrong (in C): in C rand() returns an integer in some range. Thus there is a non-zero probability it returns 0, and there is a non-zero probability that x is infinity and the loop never terminates. If a discrete random variable has a non-zero probability of being infinity, then its expected value is infinite. So I think gnasher729 is right, and technically the average running time is infinite. $\endgroup$ – D.W. Jul 13 '17 at 17:39
  • $\begingroup$ @D.W. That's what I asked in comment. So, if there is only one of thousands cases that never halts, average runtime is infinite? $\endgroup$ – rus9384 Jul 13 '17 at 18:34
  • $\begingroup$ @D.W. Actually, if $y$ is 0 then there is a division-by-zero exception (there's another exception if $x=0$). I think that the interesting way to play this game is to take the limit $N\to\infty$. $\endgroup$ – Yuval Filmus Jul 13 '17 at 21:33
2
$\begingroup$

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$?

| cite | improve this answer | |
$\endgroup$
  • 3
    $\begingroup$ This doesn't quite answer the question, since we're interested in the average case. $\endgroup$ – Yuval Filmus Jul 13 '17 at 16:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.