Back

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: 2014 Fall Midterm - 13

Author: Michiel Smid

Question

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) = 2 \log n\ \mathrm{for}\ n \geq 1.$
(b)
$F(n) = (2 \log n) - 1\ \mathrm{for}\ n \geq 2.$
(c)
$F(n) = (2 \log n) - 1\ \mathrm{for}\ n \geq 1.$
(d)
$F(n) = \log n\ \mathrm{for}\ n \geq 1.$

Solution

Let’s test it out $(f(1)=0)$

$f(2)=1$

$f(4)=3$

$f(8)=5$

$f(16)=7$

$f(32)=9$

  • a) $f(32)=log{32}=5$
  • b) $f(32)=2log{32}=10$
  • c) $f(32)=2log{32}-1=9$
    $f(1)=2 log{1}-1=-1$
  • d) $f(32)=2log{32}-1=9$
    $f(2)=2 log{2}-1=1$

As can be seen, (d) gives the most appropriate response