Consider the following recursive algorithm $\Silly$, which takes as input an integer $n \geq 1$ which is a power of 2:

$\mathbf{Algorithm}\ \Silly(n)\mathrm{:}$
$\mathbf{if}\ n = 1$
$\mathbf{then}\ \text{drink one pint of beer}$
$\mathbf{else}\ \mathbf{if}\ n = 2$
$\elsesp \mathbf{then}\ \text{fart once}$
$\elsesp \mathbf{else}\ \text{fart once};$
$\elsesp \elsesp \Silly(n / 2);$
$\elsesp \elsesp \text{fart once}$
$\elsesp \mathbf{endif}$
$\mathbf{endif}$

For $n$ a power of 2, let $F(n)$ be the number of times you fart when running algorithm $\Silly(n)$. Which of the following is true?
(n.b., $\log$ denotes the base-2 logarithm)

a) $F(n) = \log n\ \mathrm{for}\ n \geq 1.$

b) $F(n) = 2 \log n\ \mathrm{for}\ n \geq 1.$

c) $F(n) = (2 \log n) - 1\ \mathrm{for}\ n \geq 1.$

d) $F(n) = (2 \log n) - 1\ \mathrm{for}\ n \geq 2.$

Solution