Solution: 2015 Winter Midterm - 14

Author: Michiel Smid

Question

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) = 2n - 1$

(b)

$S(n) = 2n + 1$

(c)

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

(d)

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

Solution

We can calculate the first couple of values of $S(n)$ to see if we can find a pattern.

$S(1) = 1$

$S(2) = 3$

$S(n)=1+logn$
$S(2) = 1+log{2} = 1+1 = 2$
$S(n)=2+nlogn$
$S(2) = 2+2 log{2} = 2+2 = 4$
$S(n)=2n+1$
$S(2) = 2 \cdot 2 + 1 = 5$
$S(n)=2n-1$
$S(2) = 2 \cdot 2 - 1 = 3$

Therefore, we know that $S(n)=2n-1$ is the correct answer.