CODEWITHSUNDEEP
time-complexityprobability
vdangre
vdangre

Reputation: 33

Time complexity of probabilistic algorithm

The game is simple: a program has to 'guess' some given n such that 1 < n < N, where n and N are positive integers. Assuming I'm using a true random number generator function ( rng() ) to generate the computer's 'guess', the probability that it will 'guess' the given n at any try is 1/N.

Example pseudo-code:

n = a // we assign some positive integer value to n

N = b // we assign some positive integer value to N

check loop
{
   if rng(N) = n
      print some success message
      exit program
   else 
      back to the beginning of the check loop
}

OK, I'm interested in how do I determine the time complexity (the upper bound especially) of this algorithm? I'm kind of confused. How does the probability aspect affect this? If I understand correctly, the worst case scenario (in theory) is that the program runs forever?

Upvotes: 2

Views: 1138

Answers (1)

Alex Salauyou
Alex Salauyou

Reputation: 14338

Even if theoretically your program can run forever, complexity here is O(n) - because doubling n you're halving probability of guessing particular value on every step, thus doubling number of steps. Even if program could run forever with given n, it would run twice forever if n is 2 times bigger.

Complexity in O notation doesn't tell you how many operations will be performed. It tells you how number of operations depends on input size.

Upvotes: 1

Related Questions