-1

I don't know if this has been asked but consider the below program.

Doubt 1

Can I calculate an approx. complexity for this program ? (worst/best/avg.)

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

int main()
{
    srand(time(NULL));
    int no;
    while((no=rand()))
    printf("Hello world!\n");
    return 0;
}

In this question OP has calculated the complexity of a problem which uses random numbers, but i don't know how to do this calculation.

In Java the random gen. would take O(1) regardless of the seed.

Would this program have a constant time complexity (as it doesn't depend on any other factors/inputs)?

Doubt 2

int main()
    {
        while(1){
           //some action
        }
        return 0;
    }

Complexity for this problem?

Does infinite loop make the problem deterministic?

Community
  • 1
  • 1
boxed__l
  • 1,334
  • 1
  • 10
  • 24
  • 7
    There is no input to this program. How could this have a time complexity figure then? Another grasp: time complexity is for **deterministic** algorithms. Of course, easy random is not that random most of the time, but then again: I would not call it deterministic if the iterations depend on a (pseudo) random value. – ppeterka Sep 07 '13 at 21:33
  • @ppeterka66 Should i keep the question open ? or delete it? – boxed__l Sep 07 '13 at 21:40
  • There is no input at all. It is possible to estimate the complexity of the function rand(), but not of the program itself, because its duration depends on a random seed. – pablo1977 Sep 07 '13 at 21:43
  • Actually I don't know if it should be closed or not. Would someone profit from reading this? Or would one even be able find it if in need of this information? Frankly, I'm at a loss on _this_ question... – ppeterka Sep 07 '13 at 21:44
  • 1
    @ppeterka66: time complexity of randomized algorithms is equally important as for deterministic ones. – Fred Foo Sep 07 '13 at 21:55
  • @larsmans thinking of it a bit: yes it is true. With a bit of knowledge on probability calculus (where I might fall short, to be honest), it seems to be totally meaningful too... It might not mean anything for a given run on a particular input, but with an arbitrarily large number of runs and inputs, it gets a meaning. Hey, randomized algorithms just started interesting me! Also, we'd have to have quite some knowledge of the probabilistic characteristics of the random function used I think. – ppeterka Sep 07 '13 at 21:59
  • @ppeterka66: even for deterministic algorithms, proving average time complexity usually requires probability theory :) – Fred Foo Sep 07 '13 at 22:16
  • If you consider the number of times you select `no` as an input and you write the code like this `while(rand() != no)` the algorithm is O(n) as stated here: http://en.wikipedia.org/wiki/Randomized_algorithm – dcaswell Sep 07 '13 at 22:21

1 Answers1

3

It depends on the implementation of rand. Only if it's implemented in such a way that every one of the UINT_MAX possible random seeds (or at least all the possible return values of time) hits zero at some point, is worst-case time complexity even defined. Otherwise, it's undefined because this is not an algorithm but a semi-algorithm at best: it's not guaranteed to terminate.

The actual complexity, then, can I think only be determined by considering a series of machines, with ever larger sizeof(time_t), since time is the only part of the program that takes any input. It's O(2^n) where n is the wordsize of the machine, since no more than that number of random seeds can exists.

On any single machine, the worst-case running-time is bounded above by some constant (which may be very large) under the assumption that rand will eventually hit zero for every seed, making it trivially O(1).

Fred Foo
  • 355,277
  • 75
  • 744
  • 836
  • And what is your take on the fact that this program does not have any input? I think in this case, there is no meaning for complexity. If you disagree, would you elaborate on this? – ppeterka Sep 07 '13 at 22:23
  • @ppeterka66: `time` takes input. – Fred Foo Sep 07 '13 at 22:23
  • Ok, point taken. What is the input length? How can you have different input lengths to this algorithm? Please don't take this personally, or as an attack of any kind, just trying to broaden my sight on something that seems utterly disturbing to me... – ppeterka Sep 07 '13 at 22:27
  • @ppeterka66: actually, that's a very good question. I'm going to change my answer, hang on. – Fred Foo Sep 07 '13 at 22:32
  • It's still O(1) or meaningless--depending on whether rand() produces numbers from a repeating sequence that includes 0 or not. – Mike Housky Sep 07 '13 at 22:44
  • ...because no matter what the size of time() return might be, srand() is only going to use a fixed number of bits from it. – Mike Housky Sep 07 '13 at 22:45
  • @MikeHousky I think larsmans meant the srand() implementation to "grow" in the series of machines too – ppeterka Sep 07 '13 at 22:46
  • @MikeHousky: see refined answer. And yes, I assume `unsigned int` to grow with `time_t`. C integer sizes are fixed per implementation, but unbounded in principle. – Fred Foo Sep 07 '13 at 22:49
  • @larsmans I get the point, and my theoretical half is smiling big, though my practicality-oriented half still feels that while it is true, didn't get us anywhere... Thanks for broadening my (our) sight! – ppeterka Sep 07 '13 at 22:52
  • As I said above, this program has one input the number Zero. – dcaswell Sep 07 '13 at 22:55
  • @ppeterka66: it's a pretty academic exercise, I'll give you that :) – Fred Foo Sep 07 '13 at 22:59
  • The complexity of the program is based on the number of times the while loop is entered. Agreed? Zero might just as well have been an input to the program. Agreed? – dcaswell Sep 07 '13 at 23:06
  • @user814064: I don't follow. The program loops until `rand()` is zero. If a program takes an integer `n` and loops `while (n--)`, you wouldn't say its only input is 0. – Fred Foo Sep 07 '13 at 23:47
  • I posted the while loop I was referring to above. Let's assume that the programs takes a series of numbers where no takes on the values 0,1,2,3 and compares using `while(rand() != no)` The program would be O(n). Assuming that the loop terminates (rand() eventually is `no`) the fact that it is using random numbers is COMPLETELY irrelevant to its complexity. – dcaswell Sep 07 '13 at 23:52
  • @user814064: on any single machine, yes. – Fred Foo Sep 08 '13 at 00:02
  • @larsmans @user814064 : Agreed that the `rand()` method makes the program NON-DETERMINISTIC. Let me change the condition then. Let the new `while` be `while(1)` what about now? Does it make it deterministic? Is the complexity computable now? – boxed__l Sep 08 '13 at 15:29
  • I decided what I thought made sense. Then I found a reference to back it up and posted it above. Maybe the wikipedia entry is wrong -- but I'm not sure that that comment section here is the best place to argue it. I googled it `"Las Vegas algorithm:" random"` there's 168,000 entries. – dcaswell Sep 08 '13 at 15:37
  • @user814064 : Thanks for the link! The code in the question is Las Vegas agreed. Now my question is, consider an infinite loop what type of problem is that? AFAIK an infinite loop is not Random. – boxed__l Sep 08 '13 at 15:46
  • I didn't understand -- sorry! If you have something you want to know -- post a question. – dcaswell Sep 08 '13 at 15:49
  • 1
    It a REAL bad idea to edit the question so that people's answers no longer match. – dcaswell Sep 08 '13 at 15:58
  • @user814064 Pls check the ques. under NEW QUESTION – boxed__l Sep 08 '13 at 16:01
  • 1
    @boxed__l: never ask a new question under an old one. It defeats the FAQ nature of SO. To answer the question, that program has no complexity because it's not implementing an algorithm. – Fred Foo Sep 08 '13 at 19:02
  • @larsmans : thanks! will keep that in mind. What if the body does perform some operation or follows some algorithm? Am i missing something very basic here about algorithms/complexities? – boxed__l Sep 08 '13 at 19:08
  • 1
    @boxed__l: it doesn't matter. A program that never terminates is not an algorithm, per definition. – Fred Foo Sep 08 '13 at 19:11
  • @larsmans : Thanks again!!. Regarding "ask a new question under an old one", how should i tackle this? That second question struck me in the comments section so i modified the question as a new question seemed to be a time consuming process. – boxed__l Sep 08 '13 at 19:17
  • 1
    @boxed__l: asking a new question is the way to go, esp. after you've already accepted an answer. My answer no longer reflects your question, which is a bit of a shame. – Fred Foo Sep 08 '13 at 19:32