How many calls to generator are made? <p>Suppose I have the following algorithm:</p> <pre><code>procedure(n) if n == 1 then break R = generaterandom() procedure(n/2) </code></pre> <p>Now I understand that the complexity of this algorithm is <code>log(n)</code> but does it make <code>log(n)</code> calls to the random generator or <code>log(n)-1</code> since it is not called for the call when <code>n==1</code>.</p> <p>Sorry if this is obvious, but i've been looking around and its not really stated anywhere what the exact answer is.</p>