Back

Question: 2016 Fall Midterm - 14

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

$\mathbf{Algorithm} \text{ ElisaDrinksCider}(n):$
$\quad \mathbf{if}\ n = 1\ \mathbf{then}$
$\quad \quad \text{order Fibonachos}$
$\quad \mathbf{else}$
$\quad \quad \ElisaDrinksCider(n / 2);$
$\quad \quad \text{drink n bottles of cider};$
$\quad \quad \ElisaDrinksCider(n / 2)$
$\quad \mathbf{endif}$

For $n$ a power of 2, let $C(n)$ be the total number of bottles of cider that you drink when running algorithm $\ElisaDrinksCider(n)$. Which of the following is true for any $n \geq 1$ that is a power of 2?
(n.b., $\log$ denotes the base-2 logarithm)
(a)
$C(n) = 2n \log n$
(b)
$C(n) = n \log n + 1$
(c)
$C(n) = n \log n - 1$
(d)
$C(n) = n \log n$