Question: 2015 Winter Midterm - 14

Author: Michiel Smid

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

$\mathbf{Algorithm}\ \NationalAnthem(n)\mathrm{:}$
$\mathbf{if}\ n = 1$
$\mathbf{then}\ \mathrm{sing}\ {\it O\ Canada}\ \mathrm{once}$
$\mathbf{else}\ \NationalAnthem(n / 2);$
$\elsesp \mathrm{sing}\ {\it O\ Canada}\ \mathrm{once};$
$\elsesp \NationalAnthem(n / 2)$
$\mathbf{endif}$

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

(a)

$S(n) = 1 + \log n$

(b)

$S(n) = 2n - 1$

(c)

$S(n) = 2n + 1$

(d)

$S(n) = 1 + n \log n$