title: Time complexity of probabilistic algorithm
body: <p>The game is simple: a program has to 'guess' some given n such that 1 &lt; n &lt; 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. </p>
  
  <p>Example pseudo-code:</p>
  
  <pre><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
  }
  </code></pre>
  
  <p>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?</p>